oj.uz

Submission #538338

# Submission time Handle Problem Language Result Execution time Memory
538338 2022-03-16T15:36:46 Z Sorting Carnival (CEOI14_carnival) C++17
100 / 100
 16 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 150 + 3;

int n;
int t[N], types = 1;
vector<int> v;

int query(const vector<int> &v){
    cout << v.size() << " ";
    for(int x: v)
        cout << x << " ";
    cout << endl;

    int res;
    cin >> res;
    return res;
}

int query(const vector<int> &v, int pos, int x){
    vector<int> v2 = v;
    while(v2.size() > pos)
        v2.pop_back();
    v2.push_back(x);
    return query(v2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    t[1] = 1;
    v.push_back(1);

    for(int i = 2; i <= n; ++i){
        int l = 0, r = (int)v.size();
        while(l != r){
            int mid = (l + r + 1) >> 1;
            if(query(v, mid, i) == mid + 1)
                l = mid;
            else
                r = mid - 1;
        }
        
        if(l == (int)v.size()){
            v.push_back(i);
            t[i] = ++types;
        }
        else{
            t[i] = t[v[l]];
        }
    }

    cout << "0 ";
    for(int i = 1; i <= n; ++i)
        cout << t[i] << " ";
    cout << endl;
}

Compilation message

carnival.cpp: In function 'int query(const std::vector<int>&, int, int)':
carnival.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     while(v2.size() > pos)
      |           ~~~~~~~~~~^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 312 KB Output is correct
2 Correct 8 ms 308 KB Output is correct
3 Correct 13 ms 248 KB Output is correct
4 Correct 13 ms 316 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 8 ms 300 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 10 ms 312 KB Output is correct
3 Correct 9 ms 320 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 5 ms 312 KB Output is correct
7 Correct 7 ms 208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 6 ms 324 KB Output is correct
4 Correct 12 ms 328 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 7 ms 208 KB Output is correct
7 Correct 10 ms 208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 14 ms 324 KB Output is correct
4 Correct 16 ms 328 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 10 ms 316 KB Output is correct
7 Correct 8 ms 208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 12 ms 324 KB Output is correct
4 Correct 15 ms 312 KB Output is correct
5 Correct 15 ms 316 KB Output is correct
6 Correct 12 ms 320 KB Output is correct
7 Correct 14 ms 324 KB Output is correct