| 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
#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,&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
");
// 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
");
else if(b1==fabs(b2))
printf("Next time
");
else printf("I agree
");
// }
}
}
return 0;
}