oj.uz

Submission #64720

# Submission time Handle Problem Language Result Execution time Memory
64720 2018-08-05T12:51:42 Z bazsi700 Carnival (CEOI14_carnival) C++14
0 / 100
 23 ms 580 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int col[151];

int query(vector<int> &v) {
    cout << v.size() << " ";
    for(int el : v) {
        cout << el << " ";
    }
    cout << "\n" << flush;
    int x;
    cin >> x;
    return x;
}

bool hasmatch(vector<int> &v, int x) {
    if(v.size() == 1) {
        v.push_back(x);
        int a1 = query(v);
        v.pop_back();
        return (a1 == 1);
    }
    int a1 = query(v);
    v.push_back(x);
    int a2 = query(v);
    v.pop_back();
    return (a1 == a2);
}

void solve(vector<int> &v, int x, int currcol) {
    if(!hasmatch(v,x)) {
        return;
    }
    if(v.size() == 1) {
        col[v[0]] = currcol;
        return;
    }
    vector<int> v1 (v.size()/2);
    vector<int> v2 (v.size()-v.size()/2);
    for(int i = 0; i < v.size()/2; i++) {
        v1[i] = v[i];
    }
    for(int i = 0; i < v.size()-v.size()/2; i++) {
        v2[i] = v[i+v.size()/2];
    }
    solve(v1,x,currcol);
    solve(v2,x,currcol);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int newcol = 1;
    for(int i = 1; i <= n; i++) {
        if(col[i] != 0) {
            continue;
        }
        vector<int> v (n-i);
        for(int j = i+1; j <= n; j++) {
            v[j-i-1] = j;
        }
        col[i] = newcol;
        solve(v,i,newcol++);


    }
    cout << "0 ";
    for(int i = 1; i <= n; i++) {
        cout << col[i] << " ";
    }
    return 0;
}

Compilation message

carnival.cpp: In function 'void solve(std::vector<int>&, int, int)':
carnival.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size()/2; i++) {
                    ~~^~~~~~~~~~~~
carnival.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size()-v.size()/2; i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 404 KB Output is correct
2 Correct 20 ms 404 KB Output is correct
3 Execution timed out 13 ms 516 KB Time limit exceeded (wall clock)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 516 KB Output is correct
2 Correct 13 ms 516 KB Output is correct
3 Execution timed out 13 ms 516 KB Time limit exceeded (wall clock)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 516 KB Output is correct
2 Correct 20 ms 548 KB Output is correct
3 Correct 23 ms 548 KB Output is correct
4 Execution timed out 8 ms 572 KB Time limit exceeded (wall clock)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 580 KB Output is correct
2 Correct 19 ms 580 KB Output is correct
3 Correct 13 ms 580 KB Output is correct
4 Execution timed out 8 ms 580 KB Time limit exceeded (wall clock)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 580 KB Output is correct
2 Correct 19 ms 580 KB Output is correct
3 Execution timed out 14 ms 580 KB Time limit exceeded (wall clock)
4 Halted 0 ms 0 KB -