Submission #287391

#	Time	Username	Problem	Language	Result	Execution time	Memory
287391		eohomegrownapps	Secret Permutation (RMI19_permutation)	C++14	60 / 100	61 ms	388 KiB

permutation

#include "permutation.h"
#include <bits/stdc++.h>
using namespace std;

//int query(std::vector<int> v);
//void answer(std::vector<int> v);

vector<int> getDifferences(vector<int> perm){
	deque<int> dq(perm.begin(),perm.end());
	int n = perm.size();

	vector<int> vals(n);
	int tot = 0;
	for (int i = 0; i<n; i++){
		vector<int> q(dq.begin(),dq.end());
		/*for (int x : q){
			cout<<x<<' ';
		}cout<<endl;*/
		vals[i]=query(q);
		tot+=vals[i];
		dq.push_back(dq.front());
		dq.pop_front();
	}
	vector<int> ans(n);
	ans[n-1]=tot/(n-1) - vals[0];
	//cout<<ans[n-1]<<'\n';
	int prev = ans[n-1];
	vals.push_back(vals[0]);
	for (int i = 0; i<n; i++){
		ans[i] = prev - (vals[i+1]-vals[i]);
		prev = ans[i];
	}
	return ans;
}

vector<bool> used;
stack<int> minv;
stack<int> maxv;
vector<int> values;
vector<int> v1;
vector<int> v1ans;
int curv = 0;
int nv;
int evals = 0;
bool rec(int ind){
	evals++;
	if (evals>1000000){
		return false;
	}
	/*cout<<ind<<endl;
	for (int i : values){
		cout<<i<<' ';
	}cout<<endl;*/
	// add element ind
	if (ind==nv){
		if (v1ans[0]!=-1){
			return false;
		}
		if (abs(values[nv-1]-values[0])==v1[nv-1]){
			v1ans = v1;
			/*cout<<"solution:"<<endl;
			for (int i : values){
				cout<<i<<' ';
			}cout<<'\n';*/
			return true;
		}
		return true;
	}
	//used[nv+x]
	//can we add?
	bool works = true;
	int qtmp = values[ind-1]+v1[ind-1];
	//cout<<"check increase "<<qtmp<<endl;
	if (max(qtmp,maxv.top())-minv.top()<nv && !used[nv+qtmp]){
		// try it
		bool popfrom = false;
		if (qtmp>maxv.top()){
			popfrom = true;
			maxv.push(qtmp);
		}
		values[ind]=qtmp;
		used[nv+qtmp]=true;
		if (!rec(ind+1)){
			works = false;
		}
		used[nv+qtmp]=false;
		if (popfrom){
			maxv.pop();
		}
	}
	if (!works){
		return false;
	}
	v1[ind-1]=-v1[ind-1];
	qtmp = values[ind-1]+v1[ind-1];
	//cout<<"check decrease "<<qtmp<<endl;
	if (maxv.top()-min(qtmp,minv.top())<nv && !used[nv+qtmp]){
		// try it
		bool popfrom = false;
		if (qtmp<minv.top()){
			popfrom = true;
			minv.push(qtmp);
		}
		values[ind]=qtmp;
		used[nv+qtmp]=true;
		if (!rec(ind+1)){
			works = false;
		}
		used[nv+qtmp]=false;
		if (popfrom){
			minv.pop();
		}
	}
	v1[ind-1]=-v1[ind-1];
	return works;
}

void solve(int n){
	vector<int> q1(n);
	for (int i = 0; i<n; i++){
		q1[i]=i+1;
	}
	v1 = getDifferences(q1);
	/*for (int i : v){
		cout<<i<<' ';
	}cout<<endl;*/
	vector<int> q2;
	for (int i = 1; i<=n; i+=2){
		q2.push_back(i);
	}
	for (int i = 2; i<=n; i+=2){
		q2.push_back(i);
	}

	used.resize(2*n+1);
	used[n]=true;
	values.resize(n);
	v1ans.resize(n,-1);
	nv = n;
	minv.push(0);
	maxv.push(0);
	bool rc = rec(1);
	//cout<<rc<<'\n';

	if (rc!=1){
		for (int i = 0; i<n; i++){
			v1[i]=abs(v1[i]);
		}
		vector<int> v2 = getDifferences(q2);
		for (int i = 0; i<n-1; i++){
			int tot;
			if (i%2==0){
				//cout<<"query "<<i/2<<'\n';
				tot = v2[i/2];
			} else {
				//cout<<"query "<<(n+1)/2+i/2<<'\n';
				tot = v2[(n+1)/2+i/2];
			}
			//cout<<tot<<'\n';
			//cout<<v1[i]<<' '<<v1[i+1]<<'\n';
			if (abs(v1[i]+v1[i+1])!=tot){
				v1[i+1]=-v1[i+1];
			}
		}
	} else {
		v1 = v1ans;
	}
	/*for (int i : v1){
		cout<<i<<' ';
	}cout<<endl;*/
	int cur = 0;
	int mn = 0;
	for (int i = 0; i<n-1; i++){
		cur+=v1[i];
		mn=min(cur,mn);
	}
	vector<int> ans(n);
	ans[0]=1-mn;
	for (int i = 1; i<n; i++){
		ans[i]=ans[i-1]+v1[i-1];
	}
	/*for (int i : ans){
		cout<<i<<' ';
	}cout<<'\n';*/
	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]
   15 |   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]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 15
• Subtask 2: 21 / 35
• Subtask 3: 30 / 50