UESTC--1269--ZhangYu Speech（模拟）

Time Limit: 1000MS

Memory Limit: 65535KB

64bit IO Format: %lld & %llu

Description

as we all know, ZhangYu(Octopus vulgaris) brother has a very famous speech - “Keep some distance from me”.

ZhangYu brother is so rich that everyone want to contact he, and scfkcf is one of them.

One day , ZhangYu brother agreed with scfkcf to contact him if scfkcf could beat him.

There are $n$ digits(lets give them indices from $1$ to $n$ and name them $a_1, a_2 … a_N$) and some queries.

for each query:

ZhangYu brother choose an index $x$ from $1$ to $n$.
For all indices $y$ ( $y$ < $x$) calculate the difference $b_y = a_x - a_y$.
Then ZhangYu brother calculate $B_1$ ，the sum of all by which are greater than $0$ , and scfkcf calculate $B_2$ , the sum of all by which are less than $0$.

if $B_1 > |B_2|$ , ZhangYu brother won and did not agree with scfkcf to contact him;

else if $B_1$ is equals to $|B_2|$ , ZhangYu brother would ignore the result;

else if $B_1$ < $|B_2|$ , ZhangYu brother lost and agreed with scfkcf to contact him.

Input

The first line contains two integers $n$, $m$ $(1 \le n,m \le 100000)$ denoting the number of digits and number of queries. The second line contains $n$ digits (without spaces) $a_1, a_2, …, a_n$.$(0 \le a_i \le 9)$

Each of next $m$ lines contains single integer $x$ $(1 \le x \le n)$ denoting the index for current query.

Output

For each of $m$ queries print “Keep some distance from me” if ZhangYu won, else print
“Next time” if ZhangYu brother ignored the result, else print
“I agree” if ZhangYu brother lost in a line - answer of the query.

Sample Input

10 3

0324152397

1

4

7

Sample Output

Next time

Keep some distance from me

I agree

Hint

It's better to use “scanf” instead of “cin” in your code.

Source

第七届ACM趣味程序设计竞赛第四场（正式赛）

每次统计x前边的0--9个数，然后输入x之后直接调用，要不然会超时

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 1010

#define MAXM 100010

#define INF 0x3f3f3f

int num[MAXM];

char s[MAXM];

int p[20],sum[MAXM*10];

struct node

{

	int p[20];

}d[MAXM*10];

int main()

{

	int n,t;

	while(scanf("%d%d\n",&n,&t)!=EOF)

	{

		scanf("%s",s+1);

		memset(sum,0,sizeof(sum));

		for(int i=1;i<=n;i++)

		{

			num[i]=s[i]-'0';

			for(int j=0;j<=9;j++)

			d[i].p[j]=d[i-1].p[j];

			d[i].p[num[i]]=d[i-1].p[num[i]]+1;

		}

		while(t--)

		{

			int x;

			scanf("%d",&x);

			int b1,b2;

			b1=b2=0;

//			if(num[x]==0)

//			printf("Next time\n");

//			else

//			{

				for(int i=0;i<=9;i++)

				{

					if(d[x-1].p[i])

					{

						if(num[x]-i>0)

						b1+=(num[x]-i)*d[x-1].p[i];

						else

						b2+=(num[x]-i)*d[x-1].p[i];

					}

				}

				if(b1>fabs(b2))

				printf("Keep some distance from me\n");

				else if(b1==fabs(b2))

				printf("Next time\n");

				else printf("I agree\n");

//			}

		}

	}

	return 0;

}

巴特西

UESTC--1269--ZhangYu Speech（模拟）

最新文章

热门文章