oj.uz

Submission #1045194

# Submission time Handle Problem Language Result Execution time Memory
1045194 2024-08-05T18:33:58 Z dpsaveslives Carnival (CEOI14_carnival) C++17
100 / 100
 5 ms 856 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 5 ms 436 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 432 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 380 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 3 ms 444 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 3 ms 600 KB Output is correct