/**
* 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
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);
| ~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
