oj.uz

Submission #710002

# Submission time Handle Problem Language Result Execution time Memory
710002 2023-03-15T02:55:18 Z vjudge1 Carnival (CEOI14_carnival) C++17
100 / 100
 23 ms 460 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define f first 
#define s second

typedef long long ll;
typedef long double ld;

const int maxn = 155;
const int inf = 1e7+5;

int n;

int crr = 1;

int ans[maxn];

int query(vector<int> vec){
    if(vec.empty())return 0;
    cout << vec.size() << " ";
    for(auto v: vec)cout << v << " ";
    cout << endl;
    int x;
    cin >> x;
    return x;
}

int cnp(int x, vector<int> lmao){
    int l = 0, r = lmao.size()-1;
    vector<int> nw = lmao;
    nw.push_back(x);
    if(query(nw) - query(lmao))return 0;
    while(l < r){
        int mid = (l+r)>>1;
        nw.clear();
        for(int j = l; j <= mid; j++)nw.push_back(lmao[j]);
        int cnt1 = query(nw);
        nw.push_back(x);
        int cnt2 = query(nw);
        if(cnt2 > cnt1)l = mid+1;
        else r = mid;
    }
    return ans[lmao[l]] = ans[x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        if(ans[i])continue;
        ans[i] = crr++;
        vector<int> vec;
        for(int j = i+1; j <= n; j++)if(!ans[j])vec.push_back(j);
        while(cnp(i, vec)){
            vec.clear();
            for(int j = i+1; j <= n; j++)if(!ans[j])vec.push_back(j);
        }
    }
    cout << "0 ";
    for(int i = 1; i <= n; i++)cout << ans[i] << " ";
    cout << endl;

    //cout << endl << clock()-START;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 336 KB Output is correct
2 Correct 13 ms 356 KB Output is correct
3 Correct 8 ms 336 KB Output is correct
4 Correct 6 ms 368 KB Output is correct
5 Correct 18 ms 344 KB Output is correct
6 Correct 15 ms 344 KB Output is correct
7 Correct 15 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 344 KB Output is correct
2 Correct 18 ms 336 KB Output is correct
3 Correct 6 ms 336 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 23 ms 324 KB Output is correct
6 Correct 14 ms 352 KB Output is correct
7 Correct 22 ms 336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 336 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 12 ms 348 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 18 ms 344 KB Output is correct
6 Correct 19 ms 348 KB Output is correct
7 Correct 17 ms 332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 352 KB Output is correct
2 Correct 18 ms 348 KB Output is correct
3 Correct 5 ms 368 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 18 ms 348 KB Output is correct
6 Correct 16 ms 328 KB Output is correct
7 Correct 18 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 360 KB Output is correct
2 Correct 15 ms 460 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 11 ms 336 KB Output is correct
5 Correct 14 ms 336 KB Output is correct
6 Correct 12 ms 336 KB Output is correct
7 Correct 6 ms 324 KB Output is correct