Submission #463839

#	Time	Username	Problem	Language	Result	Execution time	Memory
463839		mosiashvililuka	Secret Permutation (RMI19_permutation)	C++14	53.14 / 100	54 ms	332 KiB

permutation

#include<bits/stdc++.h>
#include "permutationc.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,p[1009],pi,ONE,LAST,A[4][1009],mn,f[1009];
vector <int> v,vv,ans;
void solve(int N);
int query(std::vector<int> V);
void answer(std::vector<int> P);
void Fill(vector <int>& q){
	int FX[280];
	for(int h=0; h<=a+1; h++){
		FX[h]=0;
	}
	for(int h=0; h<q.size(); h++){
		FX[q[h]]=1;
	}
	for(int h=1; h<=a; h++){
		if(FX[h]==0){
			q.push_back(h);
		}
	}
}
int diff(int Q, int q, int w){
	vector <int> qw;
	qw.clear();qw.push_back(q);qw.push_back(w);qw.push_back(Q);//A[i-1]-A[1]
	Fill(qw);
	int as=query(qw);
	qw.clear();qw.push_back(w);qw.push_back(q);qw.push_back(Q);//A[i]-A[1]
	Fill(qw);
	int sd=query(qw);
	return sd-as;
}
void solve(int N){
	a=N;
	A[1][2]=0;
	for(i=3; i<=a; i++){
		A[1][i]=A[1][i-1]+diff(1,i,i-1);
	}
	A[2][3]=A[1][2]+diff(2,3,1);
	for(i=4; i<=a; i++){
		A[2][i]=A[2][i-1]+diff(2,i,i-1);
	}
	mn=0;c=1;d=2;
	for(i=3; i<=a; i++){
		if(mn>A[1][i]){
			mn=A[1][i];c=1;d=i;
		}
		if(mn>A[2][i]){
			mn=A[2][i];c=2;d=i;
		}
	}
	//-mn
	mn--;
	for(i=2; i<=a; i++){
		if(i!=2) A[2][i]-=mn;
		A[1][i]-=mn;
	}
	
	
	/*cout<<"  ";for(i=2; i<=a; i++){
		cout<<A[1][i]<<" ";
	}
	cout<<endl;
	cout<<"  "<<"  ";for(i=3; i<=a; i++){
		cout<<A[2][i]<<" ";
	}
	cout<<endl;*/
	f[1]=0;f[2]=A[1][2];
	for(i=3; i<=a; i++){
		if(/*A[1][i]==A[2][i]+A[1][2]*/abs(A[1][i]-A[1][2])==A[2][i]){
			f[i]=f[1]+A[1][i];
		}else{
			f[i]=f[1]-A[1][i];
		}
	}
	mn=0;
	for(i=1; i<=a; i++){
		if(mn>f[i]){
			mn=f[i];
		}
	}
	mn--;
	for(i=1; i<=a; i++) f[i]-=mn;
	ans.clear();
	for(i=1; i<=a; i++){
		ans.push_back(f[i]);
	}
	answer(ans);
}




//
/*int FA[1009];
int query(vector <int> V){
	int qw=0;
	for(int h=1; h<V.size(); h++){
		qw+=abs(FA[V[h]]-FA[V[h-1]]);
	}
	return qw;
}
void answer(vector <int> P){
	for(int h=0; h<P.size(); h++){
		cout<<P[h]<<" ";
	}
	exit(0);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++){
		cin>>c;
		FA[i]=c;
	}
	solve(a);
	return 0;
}*/

Compilation message (stderr)

permutation.cpp: In function 'void Fill(std::vector<int>&)':
permutation.cpp:14:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int h=0; h<q.size(); h++){
      |               ~^~~~~~~~~
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: 7.9714350000000005 / 15
• Subtask 2: 18.600015000000003 / 35
• Subtask 3: 26.571450000000002 / 50