Submission #198092

#	Time	Username	Problem	Language	Result	Execution time	Memory
198092		model_code	Secret Permutation (RMI19_permutation)	C++17	100 / 100	2201 ms	448 KiB

permutation

/**
* user:  pavic-9e7
* fname: Patrick
* lname: Pavić
* task:  permutation
* score: 100.0
* date:  2019-10-11 08:46:49.328394
*/
#include "permutation.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 505;

int raz[N], bio[N], n;
vi cur, p;
vector < pair < vi , int > >  qv;

bool dobar(int x){
	return !(x < 1 || x > n || bio[x]);
}

int eval(vi p, vi v){
	int ret = 0;
	for(int i = 0;i + 1 < n;i++){
		ret += abs(p[v[i] - 1] - p[v[i + 1] - 1]);
	}	
	return ret;
}

void brute(int i){
	//printf("i = %d\n", i);
	if(i == n){
		if(abs(cur.back() - cur[0]) != raz[0])
			return;
		vi fin, inv; fin.resize(n); inv.resize(n);
		for(int i = 0;i < n;i++)
			fin[p[i] - 1] = cur[i], inv[cur[i] - 1] = p[i];
		//printf("mislim da ga imam : \n");
		//for(int x : fin)
		//	printf("%d ", x);
		//printf("\n");
		
		//if(query(inv) != n - 1)
		//	return;
		answer(fin);
		return;
	}
	if(dobar(cur.back() - raz[i])){
		cur.PB(cur.back() - raz[i]);
		bio[cur.back()]++; brute(i + 1); bio[cur.back()]--;
		cur.pop_back();
	}
	if(dobar(cur.back() + raz[i])){
		cur.PB(cur.back() + raz[i]);
		bio[cur.back()]++; brute(i + 1); bio[cur.back()]--;
		cur.pop_back();
	}
}

void solve(int nn) {
	n = nn;
	if(n <= 7){
		vi v, fin;
		for(int i = 0;i < n;i++){
			v.PB(i + 1); fin.PB(i + 1);
		}
		
		for(int i = 0;i < n ;i++){
			random_shuffle(v.begin(), v.end());
			random_shuffle(v.begin(), v.end());
			qv.PB({v, query(v)});
		}
		do{
			bool good = 1;
			for(pair < vi, int > q : qv){
				if(eval(fin, q.X) != q.Y){
					 //printf("%d %d\n", q.Y, eval(fin, q.X));
					 good = 0;
				}
			}		
				
			//printf("fin : ");
			//for(int x : fin) printf("%d ", x);
			//printf("\n");
			if(good){
				answer(fin);
				return;
			}
		} while(next_permutation(fin.begin(), fin.end()));	
		return;
	}
	for(int i = 0;i < n;i++){
		p.PB(i + 1);
	}
	random_shuffle(p.begin(), p.end());
	random_shuffle(p.begin(), p.end());

	int sm = 0;
	for(int i = 0;i < n;i++){
		raz[i] = query(p);
		sm += raz[i];
		p.push_back(p[0]);
		p.erase(p.begin());
	}
	sm /= (n - 1);
	for(int i = 0;i < n;i++)
		raz[i] = sm - raz[i];// printf("raz %d = %d\n", i, raz[i]);
	for(int i = n;i >= 1;i--){
		bio[i]++; cur.PB(i);
		brute(1);
		bio[i]--; cur.pop_back();
	}
}

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: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 50 / 50