제출 #871446

#제출 시각아이디문제언어결과실행 시간메모리
871446rainboySecret Permutation (RMI19_permutation)C++17
90 / 100
462 ms53952 KiB
#include "permutation.h" #include <iostream> #include <cstring> #include <vector> using namespace std; typedef vector<int> vi; const int N = 256, M = 260000; const long long INF = 0x3f3f3f3f3f3f3f3fLL; int abs_(int a) { return a > 0 ? a : -a; } int min(int a, int b) { return a < b ? a : b; } unsigned int X = 133333333; int rand_() { return (X *= 3) >> 1; } char used[N]; int kk[N]; int check(short *aa, int n, int m) { int a = 0; for (int i = 0; i < m; i++) a = min(a, aa[i]); memset(used, 0, n * sizeof *used); for (int i = 0; i < m; i++) { if (aa[i] - a >= n || used[aa[i] - a]) return 0; used[aa[i] - a] = 1; } return 1; } int rr[N], dd[N]; short aaa[M][N], aaa_[M][N]; void solve(int n) { for (int i = 0; i < n; i++) rr[i] = i; for (int i = 0; i < n; i++) { int j = rand_() % (i + 1), tmp; tmp = rr[i], rr[i] = rr[j], rr[j] = tmp; } vi ii(n); for (int i = 0; i < n; i++) { for (int h = 0; h < n; h++) ii[h] = rr[(i + h) % n] + 1; dd[i] = query(ii); } int sum = 0; for (int i = 0; i < n; i++) sum += dd[i]; sum /= n - 1; for (int i = 0; i < n; i++) dd[i] = sum - dd[i]; vi aa(n), aa_(n); int m, m_; m = 0; aaa[m][0] = 0, aaa[m][1] = dd[1], m++; int j = 2; while (1) { while (j < n) { m_ = 0; for (int h = 0; h < m; h++) { memcpy(aaa_[m_], aaa[h], j * sizeof *aaa[h]), aaa_[m_][j] = aaa[h][j - 1] + dd[j]; if (check(aaa_[m_], n, j + 1)) m_++; if (m_ >= M) goto out; memcpy(aaa_[m_], aaa[h], j * sizeof *aaa[h]), aaa_[m_][j] = aaa[h][j - 1] - dd[j]; if (check(aaa_[m_], n, j + 1)) m_++; if (m_ >= M) goto out; } m = m_; for (int h = 0; h < m_; h++) memcpy(aaa[h], aaa_[h], (j + 1) * sizeof *aaa_[h]); j++; } out: if (j == n) { m_ = 0; for (int h = 0; h < m; h++) if (abs_(aaa[h][n - 1]) == dd[0]) memcpy(aaa_[m_++], aaa[h], n * sizeof *aaa[h]); m = m_; for (int h = 0; h < m_; h++) memcpy(aaa[h], aaa_[h], n * sizeof *aaa_[h]); if (m == 1) { for (int i = 0; i < n; i++) aa[i] = aaa[0][i]; break; } } long long z_ = INF; int i_ = -1; for (int i = 0; i < j; i++) { memset(kk, 0, n * sizeof *kk); for (int h = 0; h < m; h++) kk[abs_(aaa[h][i])]++; long long z = 0; for (int a = 0; a < n; a++) z += (long long) kk[a] * kk[a]; if (z_ > z) z_ = z, i_ = i; } cerr << i_ << endl; for (int h = 0; h < n; h++) ii[h] = rr[h < i_ ? i_ - 1 - h : h] + 1; int a = query(ii) - (sum - dd[0]) + dd[i_]; m_ = 0; for (int h = 0; h < m; h++) if (abs_(aaa[h][i_]) == a) memcpy(aaa_[m_++], aaa[h], n * sizeof *aaa[h]); m = m_; for (int h = 0; h < m_; h++) memcpy(aaa[h], aaa_[h], n * sizeof *aaa_[h]); } int a = 0; for (int i = 0; i < n; i++) a = min(a, aa[i]); for (int i = 0; i < n; i++) aa[i] -= a - 1; for (int i = 0; i < n; i++) aa_[rr[i]] = aa[i]; for (int i = 0; i < n; i++) aa[i] = aa_[i]; answer(aa); }

컴파일 시 표준 에러 (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...