Submission #960212

#	Time	Username	Problem	Language	Result	Execution time	Memory
960212		MilosMilutinovic	Mouse (info1cup19_mouse)	C++14	40.67 / 100	113 ms	1476 KiB

mouse

#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 ans[505];

/*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;
		int sz=(int)ids.size();
		int mx=-1;
		vector<int> bst;
		for(int iter=1;iter<=sz;iter++){
			shuffle(num.begin(),num.end(),mrand);
			for(int j=0;j<sz;j++) ans[ids[j]]=num[j];
			if(chkmax(mx,ask())) bst=num;
		}
		num=bst;
		for(int i=0;i<sz;i++) ans[ids[i]]=num[i];
		if(mx==n) return;
		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 / 13
• Subtask 2: 27.66666 / 38
• Subtask 3: 0 / 49