제출 #1230786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230786		altern23	사육제 (CEOI14_carnival)	C++20	100 / 100	6 ms	596 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 150;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

ll dp[MAXN + 5][MAXN + 5], ans[MAXN + 5];
int main(){
	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		dp[1][1] = 1;
		ans[1] = 1;
		ll cur = 2;
		
		auto query = [&](ll l, ll r){
			if(dp[l][r]) return dp[l][r];
			vector<ll> v;
			for(int i = l; i <= r; i++) v.push_back(i);
			cout << (int)v.size() << " ";
			for(auto x : v) cout << x << " ";
			cout << endl;
			ll x; cin >> x;
			dp[l][r] = x;
			return x;
		};
		
		for(int i = 2; i <= N; i++){
			ll lf = 1, rg = i - 1, pt = -1;
			for(;lf <= rg;){
				ll mid = (lf + rg) / 2;
				if(query(mid, i) == query(mid, i - 1)){
					pt = mid;
					lf = mid + 1;
				}
				else rg = mid - 1;
			}
			if(pt == -1) ans[i] = cur++;
			else ans[i] = ans[pt];
			
			set<ll> st;
			for(int j = i; j >= 1; --j){
				st.insert(ans[j]);
				dp[j][i] = (int)st.size();
			}
		}
		
		cout << 0 << " ";
		for(int i = 1; i <= N; i++){
			cout << ans[i] << " ";
		}
		cout << endl;		
	}
}

/*

*/

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