oj.uz

Submission #414094

# Submission time Handle Problem Language Result Execution time Memory
414094 2021-05-30T02:22:51 Z jamezzz Mouse (info1cup19_mouse) C++17
100 / 100
 106 ms 316 KB 
#include "grader.h"

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

#define pf printf
#define sz(x) (int) (x).size()

vector<int> todo,v;
bool done[260];

int check(int x){ //swap (0,1),(2,3)...(2*x,2*x+1)
	for(int i=0;i<=x;++i){
		swap(v[todo[2*i]],v[todo[2*i+1]]);
	}
	int res=query(v);
	for(int i=0;i<=x;++i){
		swap(v[todo[2*i]],v[todo[2*i+1]]);
	}
	return res;
}

void solve(int N) {
    for(int i=1;i<=N;++i)v.push_back(i);
    while(true){
		int res=query(v);
		if(res==N)return;
		if(res==0)break;
		random_shuffle(v.begin(),v.end());
	}
    int pv=0;
    while(true){
		todo.clear();
		for(int i=0;i<N;++i)if(!done[i])todo.push_back(i);
		if(sz(todo)==0)break;
		random_shuffle(todo.begin(),todo.end());
		int tmp=check(sz(todo)/2-1);
		if(tmp==N)return;
		if(tmp==pv)continue;
		int lo=0,hi=sz(todo)/2-1,mid,res=0,nw=0;
		while(lo<=hi){
			mid=(lo+hi)/2;
			int tmp=check(mid);
			if(tmp==N)return;
			if(tmp>pv){
				res=mid;
				nw=tmp;
				hi=mid-1;
			}
			else lo=mid+1;
		}
		int a=todo[2*res],b=todo[2*res+1];
		swap(v[a],v[b]);
		if(nw==N)return;
		if(nw==pv+2){
			done[a]=true;
			done[b]=true;
		}
		else{
			int o=0;
			for(int i=0;i<N;++i){
				if(!done[i]&&i!=a&&i!=b){ o=i;break; }
			}
			swap(v[a],v[o]);
			int tmp=query(v);
			if(tmp==N)return;
			swap(v[a],v[o]);
			if(tmp>=nw)done[b]=true;
			else done[a]=true;
		}
		pv=query(v);
		if(pv==N)return;
	}
	return;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 1 ms 200 KB Correct! Number of queries: 8
3 Correct 1 ms 200 KB Correct! Number of queries: 20
4 Correct 1 ms 200 KB Correct! Number of queries: 26
5 Correct 1 ms 200 KB Correct! Number of queries: 19
6 Correct 1 ms 200 KB Correct! Number of queries: 28

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 1 ms 200 KB Correct! Number of queries: 8
3 Correct 1 ms 200 KB Correct! Number of queries: 20
4 Correct 1 ms 200 KB Correct! Number of queries: 26
5 Correct 1 ms 200 KB Correct! Number of queries: 19
6 Correct 1 ms 200 KB Correct! Number of queries: 28
7 Correct 7 ms 200 KB Correct! Number of queries: 400
8 Correct 6 ms 316 KB Correct! Number of queries: 400
9 Correct 6 ms 200 KB Correct! Number of queries: 400
10 Correct 8 ms 200 KB Correct! Number of queries: 400
11 Correct 5 ms 200 KB Correct! Number of queries: 300
12 Correct 6 ms 200 KB Correct! Number of queries: 400
13 Correct 6 ms 200 KB Correct! Number of queries: 400
14 Correct 8 ms 200 KB Correct! Number of queries: 400
15 Correct 7 ms 200 KB Correct! Number of queries: 400
16 Correct 7 ms 200 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: 24
2 Correct 1 ms 200 KB Correct! Number of queries: 8
3 Correct 1 ms 200 KB Correct! Number of queries: 20
4 Correct 1 ms 200 KB Correct! Number of queries: 26
5 Correct 1 ms 200 KB Correct! Number of queries: 19
6 Correct 1 ms 200 KB Correct! Number of queries: 28
7 Correct 7 ms 200 KB Correct! Number of queries: 400
8 Correct 6 ms 316 KB Correct! Number of queries: 400
9 Correct 6 ms 200 KB Correct! Number of queries: 400
10 Correct 8 ms 200 KB Correct! Number of queries: 400
11 Correct 5 ms 200 KB Correct! Number of queries: 300
12 Correct 6 ms 200 KB Correct! Number of queries: 400
13 Correct 6 ms 200 KB Correct! Number of queries: 400
14 Correct 8 ms 200 KB Correct! Number of queries: 400
15 Correct 7 ms 200 KB Correct! Number of queries: 400
16 Correct 7 ms 200 KB Correct! Number of queries: 400
17 Correct 93 ms 200 KB Correct! Number of queries: 2400
18 Correct 88 ms 200 KB Correct! Number of queries: 2300
19 Correct 81 ms 200 KB Correct! Number of queries: 2300
20 Correct 99 ms 200 KB Correct! Number of queries: 2400
21 Correct 84 ms 200 KB Correct! Number of queries: 2300
22 Correct 104 ms 200 KB Correct! Number of queries: 2300
23 Correct 85 ms 200 KB Correct! Number of queries: 2300
24 Correct 96 ms 200 KB Correct! Number of queries: 2400
25 Correct 106 ms 200 KB Correct! Number of queries: 2400
26 Correct 95 ms 200 KB Correct! Number of queries: 2400