Submission #259692

#	Time	Username	Problem	Language	Result	Execution time	Memory
259692		errorgorn	Secret Permutation (RMI19_permutation)	C++14	0 / 100	1 ms	256 KiB

permutation

#include "permutation.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
int val[100005];

void solve(int n) {
	vector<int> v;	
	int lo=1,hi=2;
	
	rep(x,3,n+1){
		//lets try to see if x is lowest or highest
		
		int v1,v2;
		
		v={lo,x,hi};
		rep(y,1,n+1) if (y!=lo && y!=x && y!=hi) v.push_back(y);
		
		v1=query(v);
		swap(v[0],v[1]);
		v2=query(v);
		
		if (v2<v1){
			lo=x;
			continue;	
		}
		
		v={hi,x,lo};
		rep(y,1,n+1) if (y!=lo && y!=x && y!=hi) v.push_back(y);
		
		v1=query(v);
		swap(v[0],v[1]);
		v2=query(v);
		
		if (v2<v1){
			hi=x;
			continue;	
		}
	}
	
	//cout<<lo<<" "<<hi<<endl;
	val[lo]=-1e9;
	val[hi]=1e9;
	
	rep(x,1,n+1) if (x!=lo && x!=hi){
		v={lo,hi,x};
		rep(y,1,n+1) if (y!=lo && y!=x && y!=hi) v.push_back(y);
		
		int v1,v2;
		v1=query(v);
		swap(v[0],v[1]);
		v2=query(v);
		
		val[x]=v2-v1;
	}
	
	vector<int> perm,ans(n);
	
	rep(x,1,n+1) perm.push_back(x);
	
	sort(all(perm),[](int i,int j){
		return val[i]<val[j];
	});
	
	rep(x,0,n) ans[perm[x]-1]=x+1;
	
	//for (auto &it:perm) cout<<it<<" "; cout<<endl;
	if (query(perm)!=n-1) exit(1);
	
	//for (auto &it:ans) cout<<it<<" "; cout<<endl;
	answer(ans);
}

Compilation message (stderr)

stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(stdin, "%d", &x);
   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(stdin, "%d", &N);
   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 50