Submission #953147

#TimeUsernameProblemLanguageResultExecution timeMemory
953147vjudge1Secret Permutation (RMI19_permutation)C++17
100 / 100
43 ms596 KiB
#include <iostream> #include <random> #include <algorithm> #include <vector> #include <cmath> typedef long long ll; typedef double lf; // #define DEBUG 1 using namespace std; const int MAXN = 300, B = 258; #ifndef DEBUG #include "permutation.h" #endif #ifdef DEBUG namespace LOCAL { int n, a[MAXN], q; inline void Solve() { cin >> n, q = 0; for (int i = 1; i <= n; i++) cin >> a[i]; } } int query(vector <int> p) { if (p.size() != LOCAL::n) {cout << "Query too short.\n"; exit(0);} LOCAL::q++; int sum = 0; for (int i = 0; i < LOCAL::n - 1; i++) sum += abs(LOCAL::a[p[i]] - LOCAL::a[p[i + 1]]); cout << "Query:\n"; for (int i = 0; i < LOCAL::n; i++) cout << p[i] << ' '; cout << '\n'; cout << sum << "\n"; return sum; } void answer(vector <int> p) { if (p.size() != LOCAL::n) {cout << "Answer too short.\n"; exit(0);} cout << "Queries used: " << LOCAL::q << "\n"; for (int i = 0; i < LOCAL::n; i++) cout << p[i] << ' '; cout << '\n'; exit(0); } void solve(int N); int main() { freopen("B.in", "r", stdin); freopen("B.out", "w", stdout); LOCAL::Solve(); solve(LOCAL::n); return 0; } #endif mt19937 Rand(102934); int n, idx[MAXN], a[MAXN], d[MAXN]; vector <int> qry; int ans[MAXN], rt; bool vis[MAXN << 1]; inline bool Solve(int cur, int p, int l, int r) { if (r - l > n - 1 || vis[p + B]) return 0; if (cur == n) { ans[cur] = p; if (p + d[n] == 0 || p - d[n] == 0) return rt = l, 1; return 0; } vis[p + B] = 1, ans[cur] = p; if (Solve(cur + 1, p + d[cur], l, max(r, p + d[cur]))) return 1; if (Solve(cur + 1, p - d[cur], min(l, p - d[cur]), r)) return 1; vis[p + B] = 0; return 0; } void solve(int N) { n = N; for (int i = 1; i <= n; i++) idx[i] = i; for (int i = 1; i <= n; i++) swap(idx[i], idx[Rand() % n + 1]); qry.clear(); for (int i = 1; i <= n; i++) qry.push_back(idx[i]); a[0] = query(qry); int sum = 0; for (int i = 1; i <= n - 1; i++) { qry.clear(); for (int j = i; j >= 1; j--) qry.push_back(idx[j]); for (int j = n; j > i; j--) qry.push_back(idx[j]); a[i] = query(qry), sum += a[i]; } sum -= (n - 2) * a[0], sum /= n - 1; d[n] = sum; for (int i = 1; i <= n - 1; i++) d[i] = a[0] - a[i] + d[n]; Solve(1, 0, 0, 0); qry.resize(n); qry[idx[1] - 1] = 1 - rt; for (int i = 2; i <= n; i++) qry[idx[i] - 1] = qry[idx[1] - 1] + ans[i]; answer(qry); }

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...