제출 #1143645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143645		dpsaveslives	사육제 (CEOI14_carnival)	C++17	100 / 100	4 ms	484 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
int ans[155],ress[155][155];
int query(int l, int r){ //query range l,r
    if(ress[l][r]) return ress[l][r];
    cout << r-l+1 << " ";
    for(int i = l;i<=r;++i){
        if(i != r) cout << i << " ";
        else cout << i << endl;
    }
    int ret; cin >> ret;
    ress[l][r] = ret;
    return ret;
}
int querylist(vector<int> vec){
    cout << vec.size() << " ";
    for(int i = 0;i<vec.size();++i){
        if(i != vec.size()-1) cout << vec[i] << " ";
        else cout << vec[i] << endl;
    }
    int ret; cin >> ret;
    return ret;
}
struct DSU{
    int N; vector<int> e;
    void init(int n){
        N = n;
        e = vector<int>(N+1,-1);
    }
    int finden(int x){
        if(e[x] < 0) return x;
        return (e[x] = finden(e[x]));
    }
    bool unite(int a, int b){
        a = finden(a), b = finden(b);
        if(a == b) return false;
        if(e[a] < e[b]) swap(a,b); //e[a] > e[b], so abs(e[a]) < abs(e[b])
        e[b] += e[a]; e[a] = b;
        return true;
    }
}dsu;
void divconq(int l, int r, int tar){
    if(l+1 == r){
        vector<int> vec; vec.push_back(l); vec.push_back(tar);
        int cur = querylist(vec);
        if(cur == 1){
            dsu.unite(l,tar);
        }
        else{
            dsu.unite(l+1,tar);
        }
        return;
    }
    if(l == r){
        dsu.unite(l,tar);
        return;
    }
    int mid = (l+r)>>1;
    int cur1 = query(l,mid);
    vector<int> vec;
    for(int i = l;i<=mid;++i) vec.push_back(i);
    vec.push_back(tar);
    int cur2 = querylist(vec);
    if(cur1 == cur2){
        divconq(l,mid,tar);
    }
    else{
        divconq(mid+1,r,tar);
    }
}
int main()
{
    int N; cin >> N;
    //ans[1] = 1;
    dsu.init(N);
    ress[1][1] = 1;
    for(int sz = 2;sz <= N;++sz){
        int cur = query(1,sz);
        if(cur != ress[1][sz-1]){
            continue;
        }
        divconq(1,sz-1,sz);
    }
    vector<int> pars;
    vector<int> comp(N+1,0); int C = 0;
    for(int i = 1;i<=N;++i){
        int curp = dsu.finden(i);
        for(auto x : pars){
            if(curp == dsu.finden(x)){
                comp[i] = comp[x];
                break;
            }
        }
        if(comp[i]) continue;
        ++C; comp[i] = C;
        pars.push_back(i);
    }
    cout << "0 ";
    for(int i = 1;i<=N;++i){
        if(i != N) cout << comp[i] << " ";
        else cout << comp[i] << endl;
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20