oj.uz

Submission #116938

# Submission time Handle Problem Language Result Execution time Memory
116938 2019-06-14T07:18:07 Z JohnTitor Carnival (CEOI14_carnival) C++11
100 / 100
 21 ms 428 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Carnival"
int n;
int c[151];
int ask(vector <int> v){
    if(v.size()==1) return 1;
    write(v.size());
    for(auto &x: v){
        putchar(' ');
        write(x);
    }
    putchar('\n');
    fflush(stdout);
    int res=0;
    read(res);
    return res;
}
bool is_connected(int u, vector <int> v){
    if(v.empty()) return 0;
    int cnt1=ask(v);
    v.pb(u);
    int cnt2=ask(v);
    return cnt1==cnt2;
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    int cnt=0;
    FOR(i, 1, n) if(c[i]==0){
        cnt++;
        c[i]=cnt;
        vector <int> all;
        FOR(j, i+1, n) if(c[j]==0) all.pb(j);
        if(all.empty()) continue;
        vector <int> rev;
        vector <int> now;
        while(is_connected(i, all)){
            while(all.size()>1){
                now.clear();
                while(now.size()+1<all.size()){
                    now.pb(all.back());
                    all.pop_back();
                }
                if(is_connected(i, all)){
                    for(int x: now) rev.pb(x);
                }
                else{
                    all=now;
                }
            }
            c[all[0]]=cnt;
            all=rev;
            rev.clear();
        }
    }
    write(0);
    putchar(' ');
    FOR(i, 1, n) write(c[i]), putchar(" \n"[i==n]);
    fflush(stdout);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 11 ms 384 KB Output is correct
3 Correct 9 ms 428 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 11 ms 256 KB Output is correct
6 Correct 19 ms 384 KB Output is correct
7 Correct 10 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 11 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 7 ms 256 KB Output is correct
6 Correct 21 ms 256 KB Output is correct
7 Correct 16 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 256 KB Output is correct
2 Correct 11 ms 256 KB Output is correct
3 Correct 13 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 10 ms 384 KB Output is correct
6 Correct 15 ms 256 KB Output is correct
7 Correct 15 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 256 KB Output is correct
2 Correct 13 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 10 ms 256 KB Output is correct
5 Correct 8 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct