oj.uz

Submission #413021

# Submission time Handle Problem Language Result Execution time Memory
413021 2021-05-28T04:54:44 Z maximath_1 Mouse (info1cup19_mouse) C++17
100 / 100
 92 ms 2640 KB 
#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){ // just for a safety measure
		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); // get a permutation that gets query(perm) = 0
		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); //get the count of all cyclic shifts
		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; // order of binary search the cyclic shifts
	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;
	{ // we are to find the front element
		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]); // swap to find the changing points of the values
			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){ // changing point = 1 is obvious
			front_element = asking[id_change[0]];
		}else{ // here changing point must be 2
			swap(asking[0], asking[id_change[0]]);
			swap(asking[0], asking[id_change[1]]); // you can scratch on a paper to see how this works for 2 changing points
			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]];
		}
	}
	// cout << front_element << endl;

	vector<int> active(N);
	iota(active.begin(), active.end(), 0); // active = the possible positions left
	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 ++){ // we will start processing each cyclic shift
		int offset = order_of_visit[owo];
		int last_offset = offset - 1; if(last_offset < 1) last_offset += N;

		int lf = 0, rg = (int)active.size() - 1, bts = 1; // we binary search only at the active positions
		for(int times = 0; times < get_count[offset]; times ++){
			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, active[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; // check number of collisions with the previous offset,
				for(int j : good_positions[last_offset]){
					if(j == 0) continue;
					if(j > active[md]) break;
					collide ++;
				}
				if(asking[0] == front_element) collide ++; // and beginning element

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

			if(valid_pos == -1){ // hard to explain, go find a testcase yourself to see why this is needed
				times_break_probably_because_its_first_element += get_count[offset] - times;
				assert(times_break_probably_because_its_first_element <= 1);
				break;
			} // insert new valid_pos
			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; // update possible positions
		}
		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 ++){ // update answer from the positions gotten
		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];
		}
		for(int j : good_positions[i]){
			ans[j] = v[j];
		}
	}

	int get = que(ans);
	return;
}

// Query count = (e ~ 3) + N + N + sum_{i=1}^{N}(log(i)) = NlogN + N

Compilation message

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;
      |       ^~~~~~~~~~~
mouse.cpp:170:6: warning: unused variable 'get' [-Wunused-variable]
  170 |  int get = que(ans);
      |      ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 23
2 Correct 1 ms 292 KB Correct! Number of queries: 18
3 Correct 1 ms 200 KB Correct! Number of queries: 20
4 Correct 2 ms 304 KB Correct! Number of queries: 26
5 Correct 1 ms 300 KB Correct! Number of queries: 25
6 Correct 1 ms 200 KB Correct! Number of queries: 23

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 23
2 Correct 1 ms 292 KB Correct! Number of queries: 18
3 Correct 1 ms 200 KB Correct! Number of queries: 20
4 Correct 2 ms 304 KB Correct! Number of queries: 26
5 Correct 1 ms 300 KB Correct! Number of queries: 25
6 Correct 1 ms 200 KB Correct! Number of queries: 23
7 Correct 6 ms 352 KB Correct! Number of queries: 300
8 Correct 7 ms 328 KB Correct! Number of queries: 300
9 Correct 5 ms 352 KB Correct! Number of queries: 300
10 Correct 6 ms 296 KB Correct! Number of queries: 300
11 Correct 4 ms 404 KB Correct! Number of queries: 300
12 Correct 7 ms 328 KB Correct! Number of queries: 300
13 Correct 8 ms 328 KB Correct! Number of queries: 300
14 Correct 6 ms 328 KB Correct! Number of queries: 300
15 Correct 6 ms 328 KB Correct! Number of queries: 300
16 Correct 6 ms 300 KB Correct! Number of queries: 400

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 23
2 Correct 1 ms 292 KB Correct! Number of queries: 18
3 Correct 1 ms 200 KB Correct! Number of queries: 20
4 Correct 2 ms 304 KB Correct! Number of queries: 26
5 Correct 1 ms 300 KB Correct! Number of queries: 25
6 Correct 1 ms 200 KB Correct! Number of queries: 23
7 Correct 6 ms 352 KB Correct! Number of queries: 300
8 Correct 7 ms 328 KB Correct! Number of queries: 300
9 Correct 5 ms 352 KB Correct! Number of queries: 300
10 Correct 6 ms 296 KB Correct! Number of queries: 300
11 Correct 4 ms 404 KB Correct! Number of queries: 300
12 Correct 7 ms 328 KB Correct! Number of queries: 300
13 Correct 8 ms 328 KB Correct! Number of queries: 300
14 Correct 6 ms 328 KB Correct! Number of queries: 300
15 Correct 6 ms 328 KB Correct! Number of queries: 300
16 Correct 6 ms 300 KB Correct! Number of queries: 400
17 Correct 90 ms 2640 KB Correct! Number of queries: 2200
18 Correct 79 ms 2152 KB Correct! Number of queries: 1900
19 Correct 76 ms 2220 KB Correct! Number of queries: 1900
20 Correct 78 ms 2496 KB Correct! Number of queries: 2100
21 Correct 82 ms 2412 KB Correct! Number of queries: 2000
22 Correct 75 ms 2252 KB Correct! Number of queries: 2000
23 Correct 85 ms 2440 KB Correct! Number of queries: 2100
24 Correct 92 ms 2500 KB Correct! Number of queries: 2100
25 Correct 87 ms 2312 KB Correct! Number of queries: 2000
26 Correct 76 ms 2456 KB Correct! Number of queries: 2100