Submission #1170634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170634		browntoad	Mouse (info1cup19_mouse)	C++20	38 / 100	84 ms	420 KiB

mouse

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

// #define TOAD

#ifdef TOAD
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

#ifdef TOAD
int query(vector<int> pus){
	for (auto x:pus) cout<<x<<' ';
	cout<<endl<<flush;
	int in; cin>>in;
	return in;
}
#endif

void solve(int N){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	vector<int> otot(N); // out
	REP(i, N) otot[i] = i+1; // ONE_BASE!!

	if (N <= 2){
		if (N == 1){
			query(otot);
			return;
		}
		int ret = query(otot);
		if (ret == 0){
			swap(otot[0], otot[1]);
			query(otot);
		}
		return;
	}

	vector<int> rem = otot; 
	fill(ALL(otot), -1);
	
	vector<int> ids = vector<int> (N);
	REP(i, N) ids[i] = i; // ZERO BASE!

	int okid = -1, plea = 0;
	while(1){
		shuffle(ALL(rem), rng);
		REP(j, SZ(rem)){
			otot[ids[j]] = rem[j];
		}
		vector<int> blacklist(N);
		int ret = query(otot), tret;
		if (ret == N) return;
		if (ret == plea) continue; // no new

		if (SZ(rem) < N){ // just match with the okid
			assert(okid != -1);
			REP(j, SZ(rem)){
				swap(otot[ids[j]], otot[okid]);
				tret = query(otot); if (tret == N) return;
				swap(otot[ids[j]], otot[okid]);

				if (tret - ret == -2){
					blacklist[j] = 1;
				}
			}
		}
		else{
			swap(otot[0], otot[1]);
			tret = query(otot); if (tret == N) return;
			swap(otot[0], otot[1]);

			if (tret - ret == -2){ // both are 1s
				blacklist[0] = blacklist[1] = 1;
				okid = 0;
				FOR(j, 2, N){
					swap(otot[ids[j]], otot[okid]);
					tret = query(otot); if (tret == N) return;
					swap(otot[ids[j]], otot[okid]);

					if (tret - ret == -2){
						blacklist[j] = 1;
					}
				}				
			}
			else if (tret - ret >= 0){ // both are fails
				FOR(j, 2, N){
					swap(otot[0], otot[j]);
					tret = query(otot); if (tret == N) return;
					swap(otot[0], otot[j]);
					if (tret - ret == -1){
						okid = j;
						blacklist[j] = 1;
					}
				}
			}
			else{
				swap(otot[1], otot[2]);
				tret = query(otot); if (tret == N) return;
				swap(otot[1], otot[2]);
				if (tret - ret == -1){ // either 101 or 010
					swap(otot[0], otot[2]);
					tret = query(otot); if (tret == N) return;
					swap(otot[0], otot[2]);

					if (tret - ret == -2){
						okid = 0;
						blacklist[0] = blacklist[2] = 1;
					}
					else{
						okid = 1;
						blacklist[1] = 1;
					}
				}
				else if (tret - ret  == -2){
					okid = 1;
					blacklist[1] = blacklist[2] = 1;
				}
				else{
					okid = 0;
					blacklist[0] = 1;
				}

				FOR(j, 3, N){
					assert(okid != -1);
					swap(otot[ids[j]], otot[okid]);
					tret = query(otot); if (tret == N) return;
					swap(otot[ids[j]], otot[okid]);

					if (tret - ret == -2){
						blacklist[j] = 1;
					}
				}
			}
		}


		vector<int> trem, tid;
		REP(j, SZ(rem)){
			if (!blacklist[j]) {
				trem.pb(rem[j]);
				tid.pb(ids[j]);
			}
			else{
				plea++;
				otot[ids[j]] = rem[j];
			}
		}
		rem = trem;
		ids = tid;
	}
}

#ifdef TOAD
signed main(){
	IOS();
	int n; cin>>n;
	//cout<<n/0.63 * n/2<<endl;
	solve(n);
}
#endif

• Subtask 1: 13 / 13
• Subtask 2: 25 / 38
• Subtask 3: 0 / 49