oj.uz

Submission #251991

# Submission time Handle Problem Language Result Execution time Memory
251991 2020-07-23T13:30:52 Z aloo123 Carnival (CEOI14_carnival) C++14
100 / 100
 21 ms 392 KB 
		#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
// #define ld long int
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(155); // TODO : change value as per problem
const ll MOD = 1e9+7;
int parent[N];
int size[N];
bool vis[N];
void make_set(int v) {
    parent[v] = v;
    size[v] = 1;
}
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (size[a] < size[b])
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}
void solve(){
	int n;
	cin >> n;
	vector<int> heads;
	heads.pb(1);
	make_set(1);
	for(int i =2;i<=n;i++){
		int curheads = heads.size();
		heads.pb(i);
		cout <<heads.size() << " ";
		for(auto h:heads) cout << h << " ";
		cout << endl;
		fflush(stdout);
		int kinds; 
		cin >> kinds;
		if(kinds == curheads){
			heads.pop_back();
			for(auto u:heads){
				cout << 2 << " " << u << " " << i << endl;
				fflush(stdout);
				int k;
				cin >> k;
				if(k == 1){
					make_set(i);
					union_sets(i,u);
					break;
				}	
			}
		}
		else{
			make_set(i);
		}
	}
	cout << 0 << " ";
	int c = 1;
	for(int i = 1;i<=n;i++){
		if(vis[i] == false){
			for(int j = 1;j<=n;j++){
				if(vis[j] == false && parent[j] == parent[i] && j!=i){
					parent[j] = c;
					vis[j] = true;
				}
			}
			vis[i] = true;
			parent[i] =c;
			c++;
		}
	}
	for(int i =1;i<=n;i++) cout << parent[i] << " ";
	cout << endl;
}	
signed main(){
 
    ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}
/*
1 2 1 3 2
2 2 0 4 1

*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 11 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 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 5 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct
3 Correct 11 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 19 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 11 ms 384 KB Output is correct
3 Correct 20 ms 384 KB Output is correct
4 Correct 17 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct