Submission #44419

#	Time	Username	Problem	Language	Result	Execution time	Memory
44419		wzy	Carnival (CEOI14_carnival)	C++11	100 / 100	22 ms	708 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
int c[160];
int dp[160][160];
int n ;

int query(int l , int r){
	if(l == r) return 1;
	cout<<(r - l + 1)<<" ";
	for(int i = l ; i <= r ;i ++){
		cout<<i<<" ";
	}
	cout<<endl;
	int x;
	cin>>x;
	return x;
}

int main(){
	cin>>n;
	for(int i = 1 ; i <=n ; i++){
		c[i] = i;
		if(i == 1){
			dp[i][i] = 1;
			for(int j = 2 ; j <= n ; j++){
				cout<<(j - i + 1)<<" ";
				for(int w = 1 ; w <= j ; w++){
					cout<<w<<" ";
				}
				cout<<endl;
				cin>>dp[i][j];
			}
		}
		else{
			int ansj = - 1;
			int l = i  , r = n;
			while(l<= r){
				int mid = (l+r)/2;
				if(dp[i-1][mid] == query(i , mid)){
					r = mid - 1;
					ansj = mid;
				}
				else{
					l = mid + 1;
				}
			}
			if(ansj == -1){
				for(int w = i ; w <= n ; w++){
					dp[i][w] = dp[i-1][w] - 1;
				}
			}
			else{
				for(int w = i ; w <=n ; w++){
					if(w < ansj) dp[i][w] = dp[i-1][w] - 1;
					else dp[i][w] = dp[i-1][w];
				}
			}
		}
	}
	for(int i =1 ; i <= n  - 1 ;i ++){
		for(int j = i + 1  ; j <= n ; j ++){
			if(dp[i][j] == dp[i+1][j]){
				c[j ] = c[i];
				break; 
			}
		}
	}
	cout<<0<<" ";
	set<int> s;
	for(int i = 1 ; i <= n; i ++){
		s.insert(c[i]);
	}
	int cnt = 0;
	map<int,int> t;
	for(set<int>::iterator it = s.begin() ; it != s.end() ; it ++ ){
		int w = *it;
		t[w] = ++cnt;
	}
	for(int i = 1 ; i <= n; i++){
		cout<<t[c[i]]<<" ";
	}
	cout<<endl;
}

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