oj.uz

Submission #47430

# Submission time Handle Problem Language Result Execution time Memory
47430 2018-05-02T22:36:37 Z TAMREF Carnival (CEOI14_carnival) C++11
100 / 100
 11 ms 576 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 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:43:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(G == R.size() + 1) continue;
            ~~^~~~~~~~~~~~~~~
carnival.cpp:35: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 7 ms 248 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 7 ms 368 KB Output is correct
4 Correct 6 ms 444 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 7 ms 576 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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