Submission #443687

#TimeUsernameProblemLanguageResultExecution timeMemory
443687valerikkSecret Permutation (RMI19_permutation)C++17
53.14 / 100
40 ms320 KiB
#include <bits/stdc++.h> #ifdef EVAL #include "permutation.h" #endif typedef long long ll; using namespace std; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); #ifndef EVAL int N; int P[256 + 10]; #endif int query_(vector<int> v) { #ifdef EVAL for (int &i : v) { i++; } return query(v); #else int sum = 0; for (int i = 1; i < v.size(); i++) sum += abs(P[v[i]] - P[v[i - 1]]); return sum; #endif } void answer_(vector<int> p) { for (int &i : p) { i++; } #ifdef EVAL answer(p); #else for (int i = 0; i < p.size(); i++) cout << p[i] << " "; #endif } void solve(int n) { auto get = [&](int a, int b, int c) { vector<int> p; for (int i = 0; i < n; i++) { if (i != a && i != b && i != c) p.push_back(i); } p.push_back(c); p.push_back(a); p.push_back(b); auto q = p; swap(q[n - 2], q[n - 1]); return query_(p) - query_(q); }; // a b // |i-a|-|b-a| int id = 1; vector<int> ord; for (int i = 2; i < n; i++) ord.push_back(i); shuffle(ord.begin(), ord.end(), rnd); for (int i : ord) { if (get(id, i, 0) < 0) id = i; } vector<pair<int, int>> l, r; for (int i = 1; i < n; i++) { if (i != id) { int d = get(i, 0, id); if (d < 0) l.emplace_back(d, i); else r.emplace_back(d, i); } } vector<int> res(n); int cur = 0; res[id] = cur++; sort(l.begin(), l.end()); for (auto [d, i] : l) res[i] = cur++; res[0] = cur++; sort(r.begin(), r.end()); for (auto [d, i] : r) res[i] = cur++; answer_(res); } #ifndef EVAL int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> P[i]; P[i]--; } solve(N); } #endif

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]
   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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...