oj.uz

Submission #361782

# Submission time Handle Problem Language Result Execution time Memory
361782 2021-01-31T15:38:24 Z Marlov Carnival (CEOI14_carnival) C++14
100 / 100
 24 ms 492 KB 
/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

#define maxN 155

int N;

int p[maxN];
int r[maxN];
int ts=0;
map<int,int> toG;

int findP(int n){
	if(n==p[n]) return n;
	int np=findP(p[n]);
	p[n]=np;
	return np;
}

void combine(int a,int b){
	int p1=findP(a);
	int p2=findP(b);
	if(r[p1]<r[p2]) swap(p1,p2);
	r[p1]=max(r[p1],r[p2]+1);
	p[p2]=p1;
}


int query(int a,int b,int x=0){
	if(a==b&&x==0) return 1;
	int sv=(b-a)+1;
	if(x!=0) sv++;
	cout<<sv<<" ";
	for(int i=a;i<=b;i++){
		cout<<i<<" ";
	}
	if(x!=0) cout<<x<<" ";
	cout<<endl;
	int res;
	cin>>res;
	return res;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N;
	for(int i=1;i<=N;i++){
		p[i]=i;
		r[i]=0;
	}

	for(int i=1;i<N;i++){
		int toI=query(i+1,N,i);
		int toE=query(i+1,N);
		if(toI==toE+1) continue;
		int a=i+1;
		int b=N;
		while(a<b){
			int mid=(a+b)/2;
			toI=query(a,mid,i);
			toE=query(a,mid);
			if(toI==toE) b=mid;
			else a=mid+1;
		}
		//cout<<"SET: "<<i<<" "<<a<<endl;
		combine(i,a);
	}

	cout<<"0 ";
	for(int i=1;i<=N;i++){
		int cp=findP(i);
		if(toG.count(cp)==0){
			toG[cp]=ts;
			ts++;
		}
		cout<<toG[cp]+1<<" ";
	}
	cout<<endl;
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 364 KB Output is correct
2 Correct 16 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 20 ms 364 KB Output is correct
6 Correct 20 ms 364 KB Output is correct
7 Correct 13 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 364 KB Output is correct
2 Correct 24 ms 364 KB Output is correct
3 Correct 15 ms 364 KB Output is correct
4 Correct 6 ms 364 KB Output is correct
5 Correct 17 ms 364 KB Output is correct
6 Correct 17 ms 364 KB Output is correct
7 Correct 20 ms 364 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 364 KB Output is correct
2 Correct 18 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 17 ms 364 KB Output is correct
6 Correct 15 ms 364 KB Output is correct
7 Correct 18 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 364 KB Output is correct
2 Correct 20 ms 364 KB Output is correct
3 Correct 12 ms 364 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 13 ms 492 KB Output is correct
6 Correct 8 ms 364 KB Output is correct
7 Correct 6 ms 364 KB Output is correct