11991 - Easy Problem from Rujia Liu?

[iriz7482]

hello everyone, sorry for creating this thread if you think it's useless
I had got TLE in this problems many times and after 6 tries I got AC in 0.104 sec using my struct . But I found some guys got AC in about 0.08 or even 0.03 ~ 0.05 . I tried coding like this and send to judge to find out how long it takes to input/output, it was about 0.080 . So I'm confused how they got AC under 0.08 , is there any way to get fast I/O?

Code: Select all

#include<stdio.h>

main()
{
     int m, n, a, k, v, i;
     while(scanf("%d %d",&m,&n)==2)
     {
          for(i=0; i<m; i++)
          {
               scanf("%d",&a);
          }
          while(n-- > 0)
          {
               scanf("%d %d",&k,&v);
               printf("0\n");
          }
     }
}

[rujialiu]

Does the following code make sense to you?

Code: Select all

inline int readint() {
  char c = getchar();
  while(!isdigit(c)) c = getchar();

  int x = 0;
  while(isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }    
  return x;
}

BTW: You don't need this kind of tricks to get AC for any problem in this problemset. In most cases I/O is not the bottleneck.

[MRH]

@ rujialiu

I try to solved this problem this way:

i take 3 parallel array
1=> For frequency of each number
2=>For last position of given numbers
3=>For parent of each index of given numbers.

Now when i take a query only i take the last position of this number and from last to climbing first position and check the frequency.

This algorithm Give TLE.
Please explain me why it give TLE.
sorry my poor English.
Thanks in advance.

[iriz7482]

@ Rujialiu
I found that using fread/fwrite can get I/O much faster but I don't know how to use them
BTW, this is a nice problem. I think it can't be solve without using suitable data structure

[rujialiu]

@MRH

if i understand your algorithm correctly, if all the numbers are equal, each query would be linear on average, so TLE

[shaon_cse_cu08]

Hai.. I have tried it with a structure...1st i store every data with there position in the input....aftef dat i sorted them to apply Binary search... dan from the 1st occurance i jumped to k-th occurance...If the number equals to 'v' dan i hv printed the actual location... I can't find any critical input for which my code fails....please provide me some critical input....This is my WA code....

Code: Select all

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct fnd
{
	long num;
	long ind;
};

bool comp(fnd a,fnd b)
{
	return a.num<b.num;
}
int b_src(fnd a[],long n,long x);

int main()
{
	struct fnd a[100001];

	long n,m,k,v,i,j,loc,count;

	while(scanf("%ld %ld",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%ld",&a[i].num);
			a[i].ind=i;
		}
		
		sort(a,a+n+1,comp);


		for(j=0;j<m;j++)
		{
			scanf("%ld %ld",&k,&v);

			loc=count=0;
			
			loc=b_src(a,n,v);


			for(i=loc;i>0;i--)
			{
				if(a[i].num!=v)
				{
					loc=i+k;
					break;
				}
			}
			
			if(i==0)
				loc=k;

			if(a[loc].num==v)
				printf("%ld\n",a[loc].ind);
			else
				printf("0\n");
		}
	}
return 0;
}

int b_src(fnd a[],long n,long x)			
{										
	int ini,end,mid;

	ini=1;
	end=n;

	while(ini<=end)
	{
		mid=(ini+end)/2;

		if(x==a[mid].num)
			return (mid);				
		
		else if(x>a[mid].num)
			ini=mid+1;
		
		else
			end=mid-1;
	}

return 0;
}

[uvasarker]

Anyone will help me please. I am getting TLE. Please help me so that I can get rid of this problem.
Here is my code:

Code: Select all

#include <cstdio>
#include <cmath>

int main()
{
	unsigned long n,m, in[1000000];
	while(scanf("%lu %lu",&n,&m)==2)
	{
			for(unsigned long i=0 ; i<n ; i++)
				scanf("%lu",&in[i]);
			unsigned long k,v, fag,times;
			for(unsigned long i=0 ; i<m ; i++)
			{
					fag=0, times=0;
					scanf("%lu %lu",&k,&v);
					for(unsigned long j=0 ; j<n ; j++)
					{
							if(v==in[j])
							{
									times++;
							}
							if(times==k)
							{
									printf("%lu\n",j+1);
									fag=1;
									break;
							}
					}
					if(fag==0)
						printf("0\n");
			}
	}
	return 0;
}

[brianfry713]

You need to precompute the answer for all possible queries.

[atiburrahman09]

I need some Help....
i am trying to solve this problem. but i cann't understand this line.

"For each query, print the 1-based location of the occurrence. If there is no such element, output 0 instead."

Any help will be great....

[brianfry713]

Sample Input

Code: Select all

8 4
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2

Sample Output

Code: Select all

2
0
7
0

The array has 8 elements, position 1 through 8. First you are looking for the first 3, that is at position 2 in the array. Next you want the second 4, but since there is only one 4 print 0 instead. Next the third 2, which is at position 7. Finally the fourth 2, but there are only three 2's, so print 0 instead.

[esharif]

I can't continue without WA or TL, I'm verily in downgrade.
but I wanna solve problems, help me to this approach. Firstly see the code below:

Code: Select all

#include<stdio.h>

int main()
{
    long int i, j, s, count, n, m, k, v, a[100001];
    while(scanf("%ld%ld",&n, &m)==2)
    {
        for(i=1; i<=n; i++)
        {
            scanf("%ld", &a[i]);
        }
        for(j=1; j<=m; j++)
        {
            count=0, s=0;
            scanf("%ld%ld", &k, &v);
            for(i=0; i<=n; i++)
            {
                if(a[i]==v)
                    count++;
                if(count==k)
                {
                    s=i;
                    break;
                }
            }
            printf("%ld\n", s);
        }
    }
    return 0;
}

[brianfry713]

You need to precompute the answer for all possible queries.

[wonderful008]

I used C with linked list to solve this problem.
But there is still some run time errors...
I could not find out them, help, please...

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAX 255
typedef struct list_node *list_ptr;
struct list_node {
	int data;
	list_ptr link;       
	};

list_ptr create(int data);


int main()
{
	int len, num, data, temp, i = 0;
	int value, times, none;
	scanf("%d %d", &len, &num);
	list_ptr node[MAX];
	temp = len;

	while (temp--) {
		none = scanf("%d", &data);
		node[i++] = create(data);
	}
	
	while (num--) {
		int count = 0;
		scanf("%d %d", &times, &value);
		for (i = 0; i < len; i++) {
			if (node[i]->data == value)
				count++;
		}
		int count2 = 0;
		if (count >= times) {
			for (i = 0; i < len; i++) {
				if (node[i]->data == value)
					count2++;
				if (count2 == times) {
					printf("%d\n", i+1);
					break;
				}
			}
		}
		else
			printf("0\n");
	}

	
	return 0;
}

list_ptr create(int data)
{
	list_ptr node;
	node = (list_ptr)malloc(sizeof(16));
	node->data = data;
	node->link = NULL;
	
	return node;
}

[brianfry713]

Try the gift I/O files for problem E at http://uva.onlinejudge.org/contests/278 ... _files.zip

[zlshang]

Hello everyone This problem I want to solve with binary search. But in the end ,I found I was fault .Every samples I can thought is OK in this code ,but I continuely got WA.I can't find any criticle input for which my codes fails....please provide me some criticle input...PLZZZZZZZ....

Code: Select all

#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <cmath>
using namespace std;
int n,m,a[1000001],b[1000001],c[1000000],k,v;
bool  cmp(int x,int y)
{
	return a[x]<a[y];	
} 

int find( )
{
	int left=0,right=n-1,mid;
	while(left<right)
		{
			mid=(left+right)/2;	
			if(a[b[c[mid]]]<v) left=mid+1;
			else right=mid;	
		}
	return left;
}
int main()
{
	while(scanf("%d%d",&n,&m)==2)
		{
			memset(a,1,sizeof(a));
			for(int i=1;i<=n;i++)
				{
					scanf("%d",&a[i]);
					b[i]=c[i]=i;
				}
			sort(b+1,b+n+1,cmp);
			for(int i=0;i<m;i++)
				{
					int p;
					scanf("%d%d",&k,&v);
					p=find();			
					if(p==0) 
						{
							if(a[b[0]]==v) printf("%d\n",a[b[k-1]]==v? b[k-1]:0);
							else if(a[b[1]]==v) printf("%d\n",a[b[k]]==v? b[k]:0);
							else printf("0\n");				
						}
					else 
						{
					
							if(a[b[p-1]]==v) printf("%d\n",a[b[p+k-2]]==v? b[p+k-2]:0);
							else if(a[b[p]]==v) printf("%d\n",a[b[p+k-1]]==v? b[p+k-1]:0);
							else if(a[b[p+1]]==v) printf("%d\n",a[b[p+k]]==v? b[p+k]:0);
							else printf("0\n");					
						}
				}
		}
		return 0;
}
/*
8 9
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2

8 4
1 3 4 5 6 7 8 9
*/