Submission #47429

#	Time	Username	Problem	Language	Result	Execution time	Memory
47429		TAMREF	Carnival (CEOI14_carnival)	C++11	100 / 100	9 ms	692 KiB

carnival

#include <bits/stdc++.h>
using namespace std;

const int mx = 155;

int rep[mx];
int n;

int f(int x){return x == rep[x] ? x : rep[x] = f(rep[x]);}
void c(int x, int y){
    x = f(x), y = f(y);
    rep[y] = x;
}

void init(){
    cin >> n;
    iota(rep+1,rep+n+1,1);
}
void naive(){
    int q;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(f(i) != f(j)){
                cout << 2 << ' ';
                cout << f(i) << ' ' << f(j) << endl;
                cin >> q;
                if(q == 1) c(i,j);
            }
        }
    }

    map<int,int> M;
    for(int i = 1; i <= n; i++){
        if(!M[f(i)]){
            M[f(i)] = -1;
            M[f(i)] = M.size();
        }
    }
    cout << 0;
    for(int i = 1; i <= n; i++){
        cout << ' ' << M[f(i)];
    }
    cout << endl;
}

void printvec(vector<int>& Q, int s = 0, int e = -1){
    if(e < 0) e = (int)Q.size() - 1;
    for(int i = s; i <= e; i++) cout << Q[i] << ' ';
}

void dnc(int s, int e, vector<int>& V){
    if(s == e){
        V.push_back(s);
        return;
    }
    vector<int> L, R;
    int m = (s+e) >> 1;
    dnc(s,m,L);
    dnc(m+1,e,R);

    int r = R.size(), G;

    for(int &l : L){
        cout << R.size() + 1 << ' ';
        cout << l << ' ';
        printvec(R);
        cout << endl;
        cin >> G;
        if(G == R.size() + 1) continue;

        int lo = 0, mi, hi = (int)R.size() - 1;
        while(lo < hi){
            mi = (lo + hi) >> 1;
            cout << mi - lo + 2 << ' ';
            cout << l << ' ';
            printvec(R, lo, mi);
            cout << endl;
            cin >> G;
            if(G == mi - lo + 2) lo = mi + 1;
            else hi = mi;
        }

        c(l, R[lo]);
    }

    for(int &l : L) V.push_back(f(l));
    for(int &r : R) V.push_back(f(r));

    sort(V.begin(), V.end());
    V.erase(unique(V.begin(),V.end()),V.end());
}

void pro(){
    vector<int> U;
    dnc(1,n,U);
    map<int,int> M;
    for(int i = 1; i <= n; i++){
        if(!M[f(i)]){
            M[f(i)] = -1;
            M[f(i)] = M.size();
        }
    }
    cout << 0;
    for(int i = 1; i <= n; i++){
        cout << ' ' << M[f(i)];
    }
    cout << endl;
}

int main(){
    init();
    pro();
}

Compilation message (stderr)

carnival.cpp: In function 'void dnc(int, int, std::vector<int>&)':
carnival.cpp:69:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(G == R.size() + 1) continue;
            ~~^~~~~~~~~~~~~~~
carnival.cpp:61:9: warning: unused variable 'r' [-Wunused-variable]
     int r = R.size(), G;
         ^

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