oj.uz

Submission #33430

# Submission time Handle Problem Language Result Execution time Memory
33430 2017-10-25T13:51:49 Z imaxblue Carnival (CEOI14_carnival) C++14
100 / 100
 16 ms 2024 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n;
vector<int> com[155];
int query(vector<int> V, vector<int> W){
    cout << V.size()+W.size() << ' ';
    fox(l, V.size()){
        cout << V[l] << ' ';
    }
    fox(l, W.size()){
        cout << W[l] << ' ';
    }
    cout << endl;
    fflush(stdin);
    int x;
    cin >> x;
    return x;
}
int query2(vector<int> V, int L, int R, int X){
    cout << R-L+2 << ' ';
    for(int l=L; l<=R; ++l){
        cout << V[l] << ' ';
    }
    cout << X << ' ';
    cout << endl;
    fflush(stdin);
    int x;
    cin >> x;
    return x;
}
vector<int> dfs(int L, int R){
    if (L==R){
        return vector<int>({R});
    }
    vector<int> v=dfs(L, (L+R)/2), w=dfs((L+R)/2+1, R), u=vector<int>();
    if (query(v, w)!=v.size()+w.size()){
        fox(l, w.size()){
            if (query2(v, 0, v.size()-1, w[l])==v.size()+1){
                u.pb(w[l]);
                continue;
            }
            //continue;
            int L=0, M, R=v.size()-1;
            while(L!=R){
                M=(L+R)/2;
                if (query2(v, L, M, w[l])!=M-L+2) R=M;
                else L=M+1;
            }
            fox(l2, com[w[l]].size()){
                com[v[L]].pb(com[w[l]][l2]);
            }
        }
    } else {
        u=w;
    }
    fox(l, u.size()) v.pb(u[l]);
    //cout << "*" << L << ' ' << R << endl;
    //fox(l, v.size()) cout << v[l] << ' '; cout << endl;
    return v;
}
int main(){
    cin >> n;
    fox1(l, n){
        com[l]=vector<int>({l});
    }
    int ans[155]={0};
    vector<int> v=dfs(1, n);
    fox(l, v.size()){
        fox(l2, com[v[l]].size()){
            ans[com[v[l]][l2]]=l+1;
        }
    }
    cout << "0 ";
    fox1(l, n){
        cout << ans[l] << ' ';
    }
    return 0;
}

Compilation message

carnival.cpp: In function 'int query(std::vector<int>, std::vector<int>)':
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:31:5: note: in expansion of macro 'fox'
     fox(l, V.size()){
     ^
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:34:5: note: in expansion of macro 'fox'
     fox(l, W.size()){
     ^
carnival.cpp: In function 'std::vector<int> dfs(int, int)':
carnival.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (query(v, w)!=v.size()+w.size()){
                    ^
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:61:9: note: in expansion of macro 'fox'
         fox(l, w.size()){
         ^
carnival.cpp:62:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (query2(v, 0, v.size()-1, w[l])==v.size()+1){
                                               ^
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:73:13: note: in expansion of macro 'fox'
             fox(l2, com[w[l]].size()){
             ^
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:80:5: note: in expansion of macro 'fox'
     fox(l, u.size()) v.pb(u[l]);
     ^
carnival.cpp: In function 'int main()':
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:92:5: note: in expansion of macro 'fox'
     fox(l, v.size()){
     ^
carnival.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
carnival.cpp:93:9: note: in expansion of macro 'fox'
         fox(l2, com[v[l]].size()){
         ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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