Submission #34577

#	Time	Username	Problem	Language	Result	Execution time	Memory
34577		Extazy	Carnival (CEOI14_carnival)	C++14	0 / 100	16 ms	2304 KiB

carnival

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 157;

int n,parents[N];
int p[N];
map < int, int > code;
bool asked[N][N];
int answer[N][N];
int f[N];
int qcnt;

int find(int x) {
    while(x!=parents[x]) {
        parents[x]=parents[parents[x]];
        x=parents[x];
    }
}

bool join(int x, int y) {
    int fx=find(x),fy=find(y);
    if(fx==fy) return false;
    if(rand()%2==0) parents[fx]=fy;
    else parents[fy]=fx;
    return true;
}

int ask(int x, int y) {
    if(asked[x][y]) return answer[x][y];
    ++qcnt;
    printf("2 %d %d\n", x, y);
    fflush(stdout);
    int ret;
    scanf("%d", &ret);
    asked[x][y]=asked[y][x]=true;
    answer[x][y]=answer[y][x]=ret;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        parents[i]=i;
    }

    while(qcnt<3500) {
        int x=1+rand()%(n-1),y=1+rand()%(n-1);
        if(y>=x) ++y;
        int ans=ask(x,y);
        if(ans==1) join(x,y);
    }

    for(i=1;i<=n;i++) f[i]=find(i),p[i]=f[i];

    sort(p+1,p+1+n);
    code[p[1]]=1;
    for(i=2;i<=n;i++) if(p[i]!=p[i-1]) code[p[i]]=code[p[i-1]]+1;

    printf("0");
    for(i=1;i<=n;i++) {
        printf(" %d", code[f[i]]);
    }
    printf("\n");
    fflush(stdout);

    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'int find(int)':
carnival.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
carnival.cpp: In function 'int ask(int, int)':
carnival.cpp:37:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ret);
                      ^
carnival.cpp: In function 'int main()':
carnival.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20