oj.uz

Submission #47429

# Submission time Handle Problem Language Result Execution time Memory
47429 2018-05-02T22:35:37 Z TAMREF Carnival (CEOI14_carnival) C++11
100 / 100
 9 ms 692 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 248 KB Output is correct
2 Correct 8 ms 436 KB Output is correct
3 Correct 7 ms 436 KB Output is correct
4 Correct 6 ms 436 KB Output is correct
5 Correct 4 ms 452 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 7 ms 624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 624 KB Output is correct
2 Correct 9 ms 624 KB Output is correct
3 Correct 6 ms 624 KB Output is correct
4 Correct 7 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 4 ms 624 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct
2 Correct 4 ms 624 KB Output is correct
3 Correct 6 ms 624 KB Output is correct
4 Correct 9 ms 692 KB Output is correct
5 Correct 5 ms 692 KB Output is correct
6 Correct 5 ms 692 KB Output is correct
7 Correct 6 ms 692 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 692 KB Output is correct
2 Correct 6 ms 692 KB Output is correct
3 Correct 9 ms 692 KB Output is correct
4 Correct 7 ms 692 KB Output is correct
5 Correct 5 ms 692 KB Output is correct
6 Correct 5 ms 692 KB Output is correct
7 Correct 8 ms 692 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 692 KB Output is correct
2 Correct 7 ms 692 KB Output is correct
3 Correct 6 ms 692 KB Output is correct
4 Correct 8 ms 692 KB Output is correct
5 Correct 7 ms 692 KB Output is correct
6 Correct 6 ms 692 KB Output is correct
7 Correct 7 ms 692 KB Output is correct