Submission #1351704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351704		ezzzay	Secret Permutation (RMI19_permutation)	C++20	50 / 100	5060 ms	1084 KiB

permutation

#include<bits/stdc++.h>
#include "permutation.h"
using namespace std;
#define pb push_back
void fun(vector<int> ans, vector<int> vis, vector<int>d, vector<int>v, int idx){
	int n=v.size();
	if(n==idx+1){
		if(d[idx]== abs(ans.back()-ans[0])){
			vector<int>x(n);
			for(int i=0;i<n;i++){
				x[v[i]-1]=ans[i];
			}
			answer(x);
		}
		return;
	}
	int c1=d[idx]+ans[idx];
	int c2=ans[idx]-d[idx];
	if(c1<=n and vis[c1]==0){
		ans[idx+1]=c1;
		vis[c1]=1;
		fun(ans,vis,d,v,idx+1);
		ans[idx+1]=vis[c1]=0;
	}
	if(c2>=1 and vis[c2]==0){
		ans[idx+1]=c2;
		vis[c2]=1;
		fun(ans,vis,d,v,idx+1);
		ans[idx+1]=vis[c2]=0;
	}
}
void solve(int n){
	vector<int>v;
	for(int i=1;i<=n;i++)v.pb(i);
	mt19937 mt(3);
	random_shuffle(v.begin(),v.end(), [&](int p){
		return mt()%p;	
	});
	
	vector<int>ans(n),d(n),vis(n+1);
	int s=0;
	for(int i=0;i<n;i++){
	    int g=v[0];
	    v.erase(v.begin());
	    v.pb(g);
		d[i]= query(v);
		s+=d[i];
	}
	s/=n-1;
	for(int i=0;i<n;i++)d[i]=s-d[i];
	
	for(int i=1;i<=n;i++){
		ans[0]=i;vis[i]=1;
		fun(ans,vis,d,v,0);
		ans[0]=vis[i]=0;
	}
}

Compilation message (stderr)

permutation.cpp: In function 'void solve(int)':
permutation.cpp:36:23: warning: 'void std::random_shuffle(_RAIter, _RAIter, _Generator&&) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Generator = solve(int)::<lambda(int)>]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   36 |         random_shuffle(v.begin(),v.end(), [&](int p){
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 |                 return mt()%p;
      |                 ~~~~~~~~~~~~~~
   38 |         });
      |         ~~             
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from permutation.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4620:5: note: declared here
 4620 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~~~~~~~~
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: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 50