oj.uz

Submission #960206

# Submission time Handle Problem Language Result Execution time Memory
960206 2024-04-09T21:59:07 Z MilosMilutinovic Mouse (info1cup19_mouse) C++14
39.3333 / 100
 110 ms 856 KB 
#include "grader.h"
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

mt19937 mrand(time(0));
int n;
int p[305],ans[305];

/*int query(vector<int> v){
	printf("? ");
	for(int i=1;i<=n;i++) printf("%d ",v[i]);
	printf("\n");
	fflush(stdout);
	int cnt=0;
	for(int i=1;i<=n;i++) cnt+=(p[i]==v[i]);
	return cnt;
}*/

int ask(){
	vector<int> v;
	for(int i=1;i<=n;i++) v.pb(ans[i]);
	int ret=query(v);
	if(ret==n) exit(0);
	return ret;
}

void solve(int n){
	::n=n;
	for(int i=1;i<=n;i++) ans[i]=0;
	function<void(vector<int>,vector<int>)> rec=[&](vector<int> ids,vector<int> num){
		if(ids.empty()) return;
		shuffle(num.begin(),num.end(),mrand);
		int sz=(int)ids.size();
		int mx=-1,bst=0;
		for(int i=0;i<sz;i++){
			for(int j=0;j<sz;j++) ans[ids[j]]=num[(i+j)%sz];
			if(chkmax(mx,ask())) bst=i;
		}
		for(int i=0;i<sz;i++) ans[ids[i]]=num[(bst+i)%sz];
		if(mx==n) return;
		assert(sz>2);
		vector<int> c(sz);
		for(int i=1;i<sz;i++){
			swap(ans[ids[0]],ans[ids[i]]);
			c[i]=ask()-mx;
			swap(ans[ids[0]],ans[ids[i]]);
		}
		bool ok=true;
		for(int i=1;i<sz;i++) if(c[i]>=0) ok=false;
		if(ok){
			bool f=false;
			for(int i=1;i<sz;i++) if(c[i]==-2) f=true;
			if(!f){
				swap(ans[ids[1]],ans[ids[2]]);
				if(ask()-mx==-2) ok=false;
				swap(ans[ids[1]],ans[ids[2]]);
			}
		}
		vector<int> nids,nnum;
		if(!ok) nids.pb(ids[0]),nnum.pb(ans[ids[0]]);
		for(int i=1;i<sz;i++){
			if(ok+c[i]>=0) nids.pb(ids[i]),nnum.pb(ans[ids[i]]);
		}
		rec(nids,nnum);
	};
	vector<int> vec;
	for(int i=1;i<=n;i++) vec.pb(i);
	rec(vec,vec);
	return;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 14
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 1 ms 344 KB Correct! Number of queries: 13
4 Correct 0 ms 344 KB Correct! Number of queries: 25
5 Correct 0 ms 344 KB Correct! Number of queries: 25
6 Correct 0 ms 344 KB Correct! Number of queries: 11

Subtask #2
26.333316 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 14
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 1 ms 344 KB Correct! Number of queries: 13
4 Correct 0 ms 344 KB Correct! Number of queries: 25
5 Correct 0 ms 344 KB Correct! Number of queries: 25
6 Correct 0 ms 344 KB Correct! Number of queries: 11
7 Correct 5 ms 700 KB Correct! Number of queries: 800
8 Correct 5 ms 696 KB Correct! Number of queries: 800
9 Correct 4 ms 696 KB Correct! Number of queries: 600
10 Correct 7 ms 700 KB Correct! Number of queries: 800
11 Correct 4 ms 704 KB Correct! Number of queries: 600
12 Correct 5 ms 448 KB Correct! Number of queries: 700
13 Correct 5 ms 704 KB Correct! Number of queries: 700
14 Correct 6 ms 856 KB Correct! Number of queries: 800
15 Correct 6 ms 700 KB Correct! Number of queries: 900
16 Correct 6 ms 452 KB Correct! Number of queries: 800

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 14
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 1 ms 344 KB Correct! Number of queries: 13
4 Correct 0 ms 344 KB Correct! Number of queries: 25
5 Correct 0 ms 344 KB Correct! Number of queries: 25
6 Correct 0 ms 344 KB Correct! Number of queries: 11
7 Correct 5 ms 700 KB Correct! Number of queries: 800
8 Correct 5 ms 696 KB Correct! Number of queries: 800
9 Correct 4 ms 696 KB Correct! Number of queries: 600
10 Correct 7 ms 700 KB Correct! Number of queries: 800
11 Correct 4 ms 704 KB Correct! Number of queries: 600
12 Correct 5 ms 448 KB Correct! Number of queries: 700
13 Correct 5 ms 704 KB Correct! Number of queries: 700
14 Correct 6 ms 856 KB Correct! Number of queries: 800
15 Correct 6 ms 700 KB Correct! Number of queries: 900
16 Correct 6 ms 452 KB Correct! Number of queries: 800
17 Runtime error 110 ms 732 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -