Submission #937576

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937576	2024-03-04T09:05:35 Z	sleepntsheep	Utrka (COCI14_utrka)	C	80 / 80	78 ms	7544 KB

utrka

#include<stdio.h>
#include<string.h>
#define N 100000
int o0[N],o1[N],n;
char s[2][N][21];

unsigned X=12345;
int rand_(){return(X*=3)>>1;}
int kk;

void sort(int*aa,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)],c;
        while(j<k) {
            c = strcmp(s[kk][aa[j]],s[kk][p]);
            if(c == 0)
                    ++j;
            else if (c < 0)
            {
                    t=aa[j], aa[j]=aa[i], aa[i]=t;
                    ++i;
                    ++j;
            }
            else
            {
                    t=aa[--k];
                    aa[k]=aa[j];
                    aa[j]=t;
            }
        }
        sort(aa,l,i);
        l=k;
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i) o0[i]=o1[i]=i, scanf("%s",s[0][i]);
    for(int i=0;i<n-1;++i) scanf("%s",s[1][i]);

    kk=0;sort(o0,0,n);
    kk=1;sort(o1,0,n-1);

    for (int l=0,i=0;i+1<n;++i,++l)
    {
        if(strcmp(s[0][o0[i]],s[1][o1[i]]))
        {
            puts(s[0][o0[i]]);
            return 0;
        }
    }
    puts(s[0][o0[n-1]]);
}

Compilation message

utrka.c: In function 'main':
utrka.c:39:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d",&n);
      |     ^~~~~~~~~~~~~~
utrka.c:40:41: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for(int i=0;i<n;++i) o0[i]=o1[i]=i, scanf("%s",s[0][i]);
      |                                         ^~~~~~~~~~~~~~~~~~~
utrka.c:41:28: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for(int i=0;i<n-1;++i) scanf("%s",s[1][i]);
      |                            ^~~~~~~~~~~~~~~~~~~

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	2 ms	2392 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2536 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	34 ms	5032 KB	Output is correct
7	Correct	54 ms	6224 KB	Output is correct
8	Correct	66 ms	7000 KB	Output is correct
9	Correct	78 ms	7544 KB	Output is correct
10	Correct	73 ms	7544 KB	Output is correct