結果
問題 | No.2577 Simple Permutation Guess |
ユーザー |
![]() |
提出日時 | 2023-12-21 00:02:08 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 2,480 bytes |
コンパイル時間 | 346 ms |
コンパイル使用メモリ | 32,656 KB |
実行使用メモリ | 25,476 KB |
平均クエリ数 | 251.74 |
最終ジャッジ日時 | 2024-09-27 10:18:14 |
合計ジャッジ時間 | 14,101 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 111 |
ソースコード
#include <stdio.h> int main () { int n = 0; int ret = 0; int res = 0; int q[400] = {}; int rem[400] = {}; int remcnt = 0; long long ans[2] = { 0LL, 1LL }; long long fact[16] = {}; res = scanf("%d", &n); for (int i = 0; i < n; i++) { rem[i] = i+1; } remcnt = n; if (n > 15) { for (int i = 0; i < n-5; i++) { int idx[2] = { 0, n-i }; while (idx[1]-idx[0] > 1) { int nxt = (idx[0]+idx[1])/2; printf("?"); for (int j = 0; j < i; j++) { printf(" %d", q[j]); } printf(" %d", rem[nxt]); for (int j = 0; j < nxt; j++) { printf(" %d", rem[j]); } for (int j = nxt+1; j < n-i; j++) { printf(" %d", rem[j]); } printf("\n"); fflush(stdout); res = scanf("%d", &ret); if (ret > 0) { idx[0] = nxt; } else { idx[1] = nxt; } } q[i] = rem[idx[0]]; for (int j = idx[0]; j < n-i-1; j++) { rem[j] = rem[j+1]; } remcnt--; } } fact[0] = 1LL; for (int i = 0; i < remcnt; i++) { fact[i+1] = fact[i]*((long long)(i+1)); } ans[1] = fact[remcnt]; while (ans[1]-ans[0] > 1LL) { int tmprem[15] = {}; long long nxt = (ans[0]+ans[1])/2LL; long long tmp = nxt; printf("?"); for (int i = 0; i < n-remcnt; i++) { printf(" %d", q[i]); } for (int i = 0; i < remcnt; i++) { tmprem[i] = rem[i]; } for (int i = 0; i < remcnt; i++) { int idx = (int)(tmp/fact[remcnt-i-1]); printf(" %d", tmprem[idx]); for (int j = idx; j < remcnt-i-1; j++) { tmprem[j] = tmprem[j+1]; } tmp %= fact[remcnt-i-1]; } printf("\n"); fflush(stdout); res = scanf("%d", &ret); if (ret > 0) { ans[0] = nxt; tmp = nxt; for (int i = 0; i < remcnt; i++) { tmprem[i] = rem[i]; } for (int i = 0; i < remcnt; i++) { int idx = (int)(tmp/fact[remcnt-i-1]); q[n-remcnt+i] = tmprem[idx]; for (int j = idx; j < remcnt-i-1; j++) { tmprem[j] = tmprem[j+1]; } tmp %= fact[remcnt-i-1]; } } else { ans[1] = nxt; } } if (ans[0] == 0LL) { for (int i = 0; i < remcnt; i++) { q[n-remcnt+i] = rem[i]; } } printf("!"); for (int j = 0; j < n; j++) { printf(" %d", q[j]); } printf("\n"); fflush(stdout); return 0; }