oj.uz

Submission #960215

# Submission time Handle Problem Language Result Execution time Memory
960215 2024-04-09T22:38:18 Z MilosMilutinovic Mouse (info1cup19_mouse) C++14
40.6667 / 100
 115 ms 1208 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,qc;
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(){
	++qc;
	assert(qc<=5000);
	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<=1;iter++){
			shuffle(num.begin(),num.end(),mrand);
			for(int i=0;i<sz;i++){
				vector<int> vec;
				for(int j=0;j<sz;j++) vec.pb(num[(i+j)%sz]);
				for(int j=0;j<sz;j++) ans[ids[j]]=vec[j];
				if(chkmax(mx,ask())) bst=vec;
			}
		}
		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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 20
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 0 ms 344 KB Correct! Number of queries: 18
4 Correct 0 ms 344 KB Correct! Number of queries: 23
5 Correct 1 ms 344 KB Correct! Number of queries: 20
6 Correct 1 ms 344 KB Correct! Number of queries: 24

Subtask #2
27.66666 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 20
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 0 ms 344 KB Correct! Number of queries: 18
4 Correct 0 ms 344 KB Correct! Number of queries: 23
5 Correct 1 ms 344 KB Correct! Number of queries: 20
6 Correct 1 ms 344 KB Correct! Number of queries: 24
7 Correct 6 ms 696 KB Correct! Number of queries: 800
8 Correct 6 ms 960 KB Correct! Number of queries: 800
9 Correct 5 ms 700 KB Correct! Number of queries: 700
10 Correct 6 ms 696 KB Correct! Number of queries: 800
11 Correct 4 ms 692 KB Correct! Number of queries: 600
12 Correct 5 ms 952 KB Correct! Number of queries: 700
13 Correct 7 ms 704 KB Correct! Number of queries: 700
14 Correct 7 ms 704 KB Correct! Number of queries: 800
15 Correct 6 ms 1208 KB Correct! Number of queries: 800
16 Correct 5 ms 700 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: 20
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 0 ms 344 KB Correct! Number of queries: 18
4 Correct 0 ms 344 KB Correct! Number of queries: 23
5 Correct 1 ms 344 KB Correct! Number of queries: 20
6 Correct 1 ms 344 KB Correct! Number of queries: 24
7 Correct 6 ms 696 KB Correct! Number of queries: 800
8 Correct 6 ms 960 KB Correct! Number of queries: 800
9 Correct 5 ms 700 KB Correct! Number of queries: 700
10 Correct 6 ms 696 KB Correct! Number of queries: 800
11 Correct 4 ms 692 KB Correct! Number of queries: 600
12 Correct 5 ms 952 KB Correct! Number of queries: 700
13 Correct 7 ms 704 KB Correct! Number of queries: 700
14 Correct 7 ms 704 KB Correct! Number of queries: 800
15 Correct 6 ms 1208 KB Correct! Number of queries: 800
16 Correct 5 ms 700 KB Correct! Number of queries: 800
17 Runtime error 115 ms 988 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -