Submission #1045194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045194		dpsaveslives	Carnival (CEOI14_carnival)	C++17	100 / 100	5 ms	856 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 152;
struct DSU{
	vector<int> d;
	DSU(int N){
	    d = vector<int> (N,-1);
	}
	int get(int x){
	    if(d[x] < 0) return x;
	    else return get(d[x]);
	}
	bool check(int a, int b){
	    return (get(a) == get(b));
	}
	bool unite(int a, int b) {
		a = get(a); b = get(b);
		if(a == b) return false;
		if(d[a] > d[b]) swap(a,b);
		d[a] += d[b]; d[b] = a;
		return true;
	}
} dsu(MAXN);
int query(vector<int> print, int newind){
    print.push_back(newind);
    cout << print.size();
    for(auto i : print) cout << " " << i;
    cout << endl;
    int ans; cin >> ans;
    return ans;
}
int divcon(vector<int> curs, int ind, int sz){
    if(sz == 1) return curs[0];
    int mid = sz/2;
    vector<int> leftside, rightside;
    for(int i = 0;i<mid;++i) leftside.push_back(curs[i]);
    for(int i = mid;i<sz;++i) rightside.push_back(curs[i]);
    int ans = query(leftside,ind);
    if(ans == mid) return divcon(leftside,ind,mid); 
    else return divcon(rightside,ind,sz-mid); 
}
int main()
{
    int N; cin >> N;
    for(int i = 2;i<=N;++i){
        vector<int> newcurs; 
        for(int j = 1;j<i;++j){
            if(dsu.get(j) == j){
                newcurs.push_back(j);
            }
        }
        int sz = newcurs.size();
        int ans = query(newcurs,i); 
        if(ans == sz+1) continue;
        ans = divcon(newcurs,i,sz);
        dsu.unite(ans,i);
    }
    int timer = 0; vector<int> answer(N+1);
	for(int i = 1;i<=N;i++){ 
		if(dsu.get(i) == i) answer[i] = ++timer;
	}
	cout << 0;
	for(int i = 1 ;i <= N;i++) cout << " " << answer[dsu.get(i)];
	cout << endl;
    return 0;
}

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