제출 #116938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116938		JohnTitor	사육제 (CEOI14_carnival)	C++11	100 / 100	21 ms	428 KiB

carnival

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20