oj.uz

Submission #44419

# Submission time Handle Problem Language Result Execution time Memory
44419 2018-04-02T05:21:55 Z wzy Carnival (CEOI14_carnival) C++11
100 / 100
 22 ms 708 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 12 ms 436 KB Output is correct
3 Correct 13 ms 540 KB Output is correct
4 Correct 22 ms 540 KB Output is correct
5 Correct 6 ms 540 KB Output is correct
6 Correct 9 ms 540 KB Output is correct
7 Correct 10 ms 616 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 616 KB Output is correct
2 Correct 11 ms 616 KB Output is correct
3 Correct 10 ms 616 KB Output is correct
4 Correct 15 ms 616 KB Output is correct
5 Correct 12 ms 652 KB Output is correct
6 Correct 9 ms 652 KB Output is correct
7 Correct 14 ms 652 KB Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 652 KB Output is correct
2 Correct 14 ms 652 KB Output is correct
3 Correct 12 ms 652 KB Output is correct
4 Correct 15 ms 652 KB Output is correct
5 Correct 14 ms 652 KB Output is correct
6 Correct 12 ms 652 KB Output is correct
7 Correct 10 ms 652 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 652 KB Output is correct
2 Correct 11 ms 700 KB Output is correct
3 Correct 14 ms 700 KB Output is correct
4 Correct 18 ms 700 KB Output is correct
5 Correct 12 ms 708 KB Output is correct
6 Correct 18 ms 708 KB Output is correct
7 Correct 18 ms 708 KB Output is correct