Submission #443722

#	Time	Username	Problem	Language	Result	Execution time	Memory
443722		valerikk	Secret Permutation (RMI19_permutation)	C++17	0 / 100	1 ms	456 KiB

permutation

/**
* user:  savkin-047
* fname: Semen
* lname: Savkin
* task:  permutation
* score: 35.0
* date:  2019-10-11 06:23:36.849875
*/
#include "permutation.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <cstring>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(const T &x, ostream &out = cerr) {
	output(x.begin(), x.end(), out);
}

template<class T> int chkmin(T &a, const T &b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmax(T &a, const T &b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int n;
vector<int> adj_abs;

int nxt(int i) {
	return (i + 1) % n;
}

int ask(vector<int> v) {
	for (int i = 0; i < v.size(); ++i) {
		v[i]++;
	}
	return query(v);
}

void norm_answer(vector<int> v) {
	int val = (*min_element(all(v)));
	for (int i = 0; i < v.size(); ++i) {
		v[i] -= (val - 1);
	}
	answer(v);
}

const int N = 270;
vector<vector<int> > var;
vector<int> cur;
int used[2 * N];

void go(int len, int val, int min_val, int max_val) {
	if (len == n) {
		if (abs(val - cur[0]) == adj_abs[n - 1]) {
			var.push_back(cur);
		}
		return;
	}
	int new_val = val + adj_abs[len - 1];
	if (max(max_val, new_val) - min(min_val, new_val) < n && used[new_val] == 0) {
		used[new_val] = 1;
		cur.push_back(new_val);
		go(len + 1, new_val, min(min_val, new_val), max(max_val, new_val));
		cur.pop_back();
		used[new_val] = 0;
	}
	if (len > 1) {
		new_val = val - adj_abs[len - 1];
		if (max(max_val, new_val) - min(min_val, new_val) < n && used[new_val] == 0) {
			used[new_val] = 1;
			cur.push_back(new_val);
			go(len + 1, new_val, min(min_val, new_val), max(max_val, new_val));
			cur.pop_back();
			used[new_val] = 0;
		}
	}
}

void solve(int _n) {
	n = _n;
	adj_abs.resize(n);
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		int pos = nxt(i);
		vector<int> cur;
		for (int j = 0; j < n; ++j) {
			cur.push_back(pos);
			pos = nxt(pos);
		}
		adj_abs[i] = ask(cur);
		sum += adj_abs[i];
	}
	sum /= (n - 1);
	for (int i = 0; i < n; ++i) {
		adj_abs[i] = sum - adj_abs[i];
	}
	cur.push_back(n);
	used[n] = 1;
	go(1, n, n, n);
	assert(var.size() == 1);
	if (var.size() == 1) {
		norm_answer(var[0]);
	}
}

Compilation message (stderr)

permutation.cpp: In function 'int ask(std::vector<int>)':
permutation.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
permutation.cpp: In function 'void norm_answer(std::vector<int>)':
permutation.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
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: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 50