oj.uz

Submission #960209

# Submission time Handle Problem Language Result Execution time Memory
960209 2024-04-09T22:33:56 Z MilosMilutinovic Mouse (info1cup19_mouse) C++14
36.6667 / 100
 119 ms 960 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 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<=n;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;
		if(sz<=2) while(true){}
		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 1 ms 344 KB Correct! Number of queries: 26
2 Correct 0 ms 344 KB Correct! Number of queries: 7
3 Correct 0 ms 344 KB Correct! Number of queries: 25
4 Correct 1 ms 344 KB Correct! Number of queries: 24
5 Correct 1 ms 344 KB Correct! Number of queries: 24
6 Correct 0 ms 344 KB Correct! Number of queries: 18

Subtask #2
23.666666 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 26
2 Correct 0 ms 344 KB Correct! Number of queries: 7
3 Correct 0 ms 344 KB Correct! Number of queries: 25
4 Correct 1 ms 344 KB Correct! Number of queries: 24
5 Correct 1 ms 344 KB Correct! Number of queries: 24
6 Correct 0 ms 344 KB Correct! Number of queries: 18
7 Correct 6 ms 700 KB Correct! Number of queries: 1000
8 Correct 7 ms 452 KB Correct! Number of queries: 1000
9 Correct 5 ms 440 KB Correct! Number of queries: 800
10 Correct 7 ms 700 KB Correct! Number of queries: 1000
11 Correct 5 ms 444 KB Correct! Number of queries: 800
12 Correct 9 ms 956 KB Correct! Number of queries: 1000
13 Correct 6 ms 704 KB Correct! Number of queries: 900
14 Correct 7 ms 956 KB Correct! Number of queries: 1100
15 Correct 8 ms 960 KB Correct! Number of queries: 1100
16 Correct 7 ms 852 KB Correct! Number of queries: 1000

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 26
2 Correct 0 ms 344 KB Correct! Number of queries: 7
3 Correct 0 ms 344 KB Correct! Number of queries: 25
4 Correct 1 ms 344 KB Correct! Number of queries: 24
5 Correct 1 ms 344 KB Correct! Number of queries: 24
6 Correct 0 ms 344 KB Correct! Number of queries: 18
7 Correct 6 ms 700 KB Correct! Number of queries: 1000
8 Correct 7 ms 452 KB Correct! Number of queries: 1000
9 Correct 5 ms 440 KB Correct! Number of queries: 800
10 Correct 7 ms 700 KB Correct! Number of queries: 1000
11 Correct 5 ms 444 KB Correct! Number of queries: 800
12 Correct 9 ms 956 KB Correct! Number of queries: 1000
13 Correct 6 ms 704 KB Correct! Number of queries: 900
14 Correct 7 ms 956 KB Correct! Number of queries: 1100
15 Correct 8 ms 960 KB Correct! Number of queries: 1100
16 Correct 7 ms 852 KB Correct! Number of queries: 1000
17 Runtime error 119 ms 724 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -