Submission #413019

#	Time	Username	Problem	Language	Result	Execution time	Memory
413019		maximath_1	Mouse (info1cup19_mouse)	C++17	100 / 100	92 ms	2592 KiB

mouse

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

map<vector<int>, int> mp;
int que(vector<int> v){
	if(mp.count(v)) return mp[v];
	return mp[v] = query(v);
}

mt19937 rng(420691273);

void solve(int N) {
	if(N <= 4){
		vector<int> v;
		for(int i = 1; i <= N; i ++)
			v.push_back(i);
		do{
			int get = que(v);
			if(get == N) return;
		}while(next_permutation(v.begin(), v.end()));
		return;
	}

	vector<int> perm(N);
	iota(perm.begin(), perm.end(), 1);
	for(;;){
		shuffle(perm.begin(), perm.end(), rng);
		int get = que(perm);
		if(get == N) return;
		if(get == 0) break;
	}
	// cout << "DONE RANDOM" << endl;
	vector<int> get_count(N + 1, 0);
	for(int i = 1; i <= N; i ++){
		vector<int> v(N);
		for(int id, j = 0; j < N; j ++){
			id = j + i;
			if(id > N) id -= N;
			v[j] = perm[id - 1];
		}
		get_count[i] = que(v);
		if(get_count[i] == N) return;
	}

	int start_from = 1;
	for(int i = 1; i <= N; i ++)
		if(get_count[i] == 0){
			start_from = i;
			break;
		}

	vector<int> order_of_visit;
	for(int i = start_from, cnt = 0; cnt < N; cnt ++){
		order_of_visit.push_back(i);
		i ++; if(i > N) i -= N;
	}

	int front_element = 0;
	{
		vector<int> asking;
		for(int j = 0; j < N; j ++){
			asking.push_back(j + start_from);
			if(asking.back() > N) asking.back() -= N;
			asking.back() = perm[asking.back() - 1];
		}
		vector<int> id_change;
		int unid_change = 0;
		for(int j = 1; j < N; j ++){
			// cout << "OWO" << endl;
			swap(asking[0], asking[j]);
			int get = que(asking);
			if(get == N) return;
			if(get != 0) id_change.push_back(j);
			else unid_change = j;
			swap(asking[0], asking[j]);
			if(id_change.size() == 2) break;
			if(get == 2) break;
		}

		if(id_change.size() == 1){
			front_element = asking[id_change[0]];
		}else{
			assert(id_change.size() == 2);
			swap(asking[0], asking[id_change[0]]);
			swap(asking[0], asking[id_change[1]]);
			int get = que(asking);
			if(get == N) return;
			swap(asking[0], asking[id_change[1]]);
			swap(asking[0], asking[id_change[0]]);
			if(get >= 2) front_element = asking[id_change[1]];
			else front_element = asking[id_change[0]];
		}
	}
	assert(front_element != 0);
	// cout << front_element << endl;

	vector<int> active(N);
	iota(active.begin(), active.end(), 0);
	int times_break_probably_because_its_first_element = 0;
	vector<vector<int> > good_positions(N + 1, vector<int>());
	for(int owo = 1; owo < N; owo ++){
		int offset = order_of_visit[owo];
		// cout << "offset now = " << offset << endl;
		int last_offset = offset - 1; if(last_offset < 1) last_offset += N;

		int lf = 0, rg = (int)active.size() - 1, bts = 1;
		for(int times = 0; times < get_count[offset]; times ++){
			// cout << "find again " << lf << " " << rg << endl;
			int valid_pos = -1;
			for(int md; lf <= rg;){
				md = (lf + rg) / 2;
				vector<int> asking;
				for(int j = 0; j < N; j ++){
					asking.push_back(j + offset);
					if(asking.back() > N) asking.back() -= N;
					asking.back() = perm[asking.back() - 1];
				}
				// rotate [0, md]
				int tmp = asking[active[md]];
				for(int j = active[md] - 1; j >= 0; j --)
					asking[j + 1] = asking[j];
				asking[0] = tmp;

				int get = que(asking);
				if(get == N) return;
				int collide = 0;
				for(int j : good_positions[last_offset]){
					if(j == 0) continue;
					if(j > active[md]) break;
					collide ++;
				}
				if(asking[0] == front_element) collide ++;
				// cout << "get " << get << " collide " << collide << ", bts " << bts << " (lf, rg) " << lf << " " << rg << endl;
				// cout << "asking ";
				// for(int ngeh : asking) cout << ngeh << " ";
				// cout << endl;

				if(get - collide >= bts){
					valid_pos = md;
					lf = md + 1;
				}else if(get - collide < bts){
					rg = md - 1;
				}
			}

			if(valid_pos == -1){
				times_break_probably_because_its_first_element += get_count[offset] - times;
				assert(times_break_probably_because_its_first_element <= 1);
				break;
			}
			rg = valid_pos; lf = 0; bts ++;
			good_positions[offset].push_back(active[valid_pos + 1]);

			vector<int> nw;
			for(int i : active)
				if(i != active[valid_pos + 1]) nw.push_back(i);
			active = nw;
		}
		reverse(good_positions[offset].begin(), good_positions[offset].end());
	}

	vector<int> ans(N, 0);
	ans[0] = front_element;
	for(int i = 1; i <= N; i ++){
		vector<int> v(N, 0);
		for(int j = 0; j < N; j ++){
			v[j] = j + i;
			if(v[j] > N) v[j] -= N;
			v[j] = perm[v[j] - 1];
		}
		// cout << "good_positions " << i << ": ";
		for(int j : good_positions[i]){
			// cout << j << " ";
			ans[j] = v[j];
		}
		// cout << endl;
	}

	int get = que(ans);
	assert(get == N);
	return;
}

Compilation message (stderr)

mouse.cpp: In function 'void solve(int)':
mouse.cpp:68:7: warning: variable 'unid_change' set but not used [-Wunused-but-set-variable]
   68 |   int unid_change = 0;
      |       ^~~~~~~~~~~

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