oj.uz

Submission #64721

# Submission time Handle Problem Language Result Execution time Memory
64721 2018-08-05T12:53:41 Z bazsi700 Carnival (CEOI14_carnival) C++14
100 / 100
 39 ms 700 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(v.empty()) {
        return;
    }
    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;
        }
        col[i] = newcol;
        if(i == n) {
            break;
        }
        vector<int> v (n-i);
        for(int j = i+1; j <= n; j++) {
            v[j-i-1] = j;
        }
        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:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size()/2; i++) {
                    ~~^~~~~~~~~~~~
carnival.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size()-v.size()/2; i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 404 KB Output is correct
2 Correct 20 ms 440 KB Output is correct
3 Correct 11 ms 440 KB Output is correct
4 Correct 15 ms 440 KB Output is correct
5 Correct 17 ms 468 KB Output is correct
6 Correct 12 ms 524 KB Output is correct
7 Correct 16 ms 524 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 652 KB Output is correct
2 Correct 39 ms 652 KB Output is correct
3 Correct 13 ms 652 KB Output is correct
4 Correct 14 ms 652 KB Output is correct
5 Correct 10 ms 652 KB Output is correct
6 Correct 4 ms 652 KB Output is correct
7 Correct 9 ms 652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 652 KB Output is correct
2 Correct 15 ms 652 KB Output is correct
3 Correct 16 ms 652 KB Output is correct
4 Correct 12 ms 652 KB Output is correct
5 Correct 11 ms 652 KB Output is correct
6 Correct 6 ms 652 KB Output is correct
7 Correct 32 ms 652 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 700 KB Output is correct
2 Correct 16 ms 700 KB Output is correct
3 Correct 20 ms 700 KB Output is correct
4 Correct 11 ms 700 KB Output is correct
5 Correct 12 ms 700 KB Output is correct
6 Correct 11 ms 700 KB Output is correct
7 Correct 12 ms 700 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 700 KB Output is correct
2 Correct 14 ms 700 KB Output is correct
3 Correct 28 ms 700 KB Output is correct
4 Correct 12 ms 700 KB Output is correct
5 Correct 7 ms 700 KB Output is correct
6 Correct 13 ms 700 KB Output is correct
7 Correct 6 ms 700 KB Output is correct