Submission #463790

#	Time	Username	Problem	Language	Result	Execution time	Memory
463790		mosiashvililuka	Secret Permutation (RMI19_permutation)	C++14	Compilation error	0 ms	0 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,vi,vvi,hja;
vector <int> v,vv,ans;
void solve(int N);
int query(std::vector<int> V);
void answer(std::vector<int> P);
void vclear(){
	vi=-1;
}
void vpush_back(int q){
	vi++;v[vi]=q;
}
void vvclear(){
	vvi=-1;
}
void vvpush_back(int q){
	vvi++;vv[vvi]=q;
}
void Fill(vector <int>& q){
	int FX[280];
	for(int h=0; h<=a+1; h++){
		FX[h]=0;
	}
	//int qi=q.size();
	int qi=vi;
	if(hja==1) qi=vvi;
	for(int h=0; h<=qi; h++){
		FX[q[h]]=1;
	}
	for(int h=1; h<=a; h++){
		if(FX[h]==0){
			//q.push_back(h);
			qi++;q[qi]=h;
		}
	}
}
void solve(int N){
	a=N;
	v.resize(a);vv.resize(a);
	for(i=1; i<=a; i++){
		vclear();pi=0;
		for(j=1; j<=a; j++){
			if(i==j) continue;
			pi++;p[pi]=j;
		}
		jj=1;
		for(j=2; j<=pi; j++){
			vclear();
			vpush_back(p[j]);vpush_back(p[jj]);vpush_back(i);
			//cout<<vi<<endl;exit(0);
			Fill(v);
			zx=query(v);
			vclear();
			vpush_back(p[jj]);vpush_back(p[j]);vpush_back(i);
			Fill(v);
			xc=query(v);
			if(xc>zx){
				jj=j;
			}
		}
		e=0;
		for(j=1; j<=pi; j++){
			if(j==jj) continue;
			vclear();
			vpush_back(p[j]);vpush_back(p[jj]);vpush_back(i);
			Fill(v);
			zx=query(v);
			vclear();
			vpush_back(p[jj]);vpush_back(p[j]);vpush_back(i);
			Fill(v);
			xc=query(v);
			//cout<<zx<<" k "<<xc<<endl;
			if(zx-xc>e){
				e=zx-xc;
			}
		}
		if(e==a-2){
			ONE=i;
			LAST=p[jj];
			break;
		}
	}
	
	/*cout<<"ONE: "<<ONE<<endl;
	exit(0);*/
	//
	if(a==3){
		vclear();vpush_back(ONE);Fill(v);
		zx=query(v);
		/*clear();vpush_back(ONE);AntiFill(v);
		xc=query(v);*/
		if(zx==2){
			vclear();vv.resize(3);vv[ONE-1]=1;vv[v[1]-1]=2;vv[v[2]-1]=3;
		}else{
			vclear();vv.resize(3);vv[ONE-1]=1;vv[v[2]-1]=2;vv[v[1]-1]=3;
		}
		answer(vv);
		return;
	}
/*	for(i=1; i<=a; i++){
		if(i==ONE) continue;
		clear();pi=0;
		for(j=1; j<=a; j++){
			if(i==j) continue;
			if(j==ONE) continue;
			pi++;p[pi]=j;
		}
		jj=1;
		for(j=2; j<=pi; j++){
			clear();
			vpush_back(p[j]);vpush_back(p[jj]);vpush_back(i);
			Fill(v);
			zx=query(v);
			clear();
			vpush_back(p[jj]);vpush_back(p[j]);vpush_back(i);
			Fill(v);
			xc=query(v);
			if(xc>zx){
				jj=j;
			}
		}
		e=0;
		for(j=1; j<=pi; j++){
			if(j==jj) continue;
			clear();
			vpush_back(p[j]);vpush_back(p[jj]);vpush_back(i);
			Fill(v);
			zx=query(v);
			clear();
			vpush_back(p[jj]);vpush_back(p[j]);vpush_back(i);
			Fill(v);
			xc=query(v);
			if(zx-xc>e){
				e=zx-xc;
			}
		}
		if(e==a-3){
			LAST=i;
			break;
		}
	}*/
	//cout<<"LAST: "<<LAST<<endl;
	ans.resize(a);
	vvclear();vvpush_back(ONE);vvpush_back(LAST);
	hja=1;Fill(vv);hja=0;
	for(i=2; i<a; i++){
		vclear();vpush_back(ONE);vpush_back(LAST);vpush_back(vv[i]);Fill(v);
		zx=query(v);
		vclear();vpush_back(LAST);vpush_back(ONE);vpush_back(vv[i]);Fill(v);
		xc=query(v);
		c=(a+1)-(zx-xc);c/=2;
		ans[vv[i]-1]=c;
	}
	ans[ONE-1]=1;ans[LAST-1]=a;
	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]<<" ";
	}
}
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 'int query(std::vector<int>)':
permutation.cpp:167:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |  for(int h=1; h<V.size(); h++){
      |               ~^~~~~~~~~
permutation.cpp: In function 'void answer(std::vector<int>)':
permutation.cpp:173:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |  for(int h=0; h<P.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);
      |   ~~~~~~^~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccu3VoDM.o: in function `query(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x1d0): multiple definition of `query(std::vector<int, std::allocator<int> >)'; /tmp/ccfYxd3Q.o:permutation.cpp:(.text+0x140): first defined here
/usr/bin/ld: /tmp/ccu3VoDM.o: in function `answer(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x280): multiple definition of `answer(std::vector<int, std::allocator<int> >)'; /tmp/ccfYxd3Q.o:permutation.cpp:(.text+0x1a0): first defined here
/usr/bin/ld: /tmp/ccu3VoDM.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfYxd3Q.o:permutation.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status