結果
問題 | No.282 おもりと天秤(2) |
ユーザー | climpet |
提出日時 | 2015-09-19 01:18:33 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 154 ms / 5,000 ms |
コード長 | 1,628 bytes |
コンパイル時間 | 669 ms |
コンパイル使用メモリ | 49,096 KB |
実行使用メモリ | 24,408 KB |
平均クエリ数 | 30.58 |
最終ジャッジ日時 | 2023-09-23 21:36:20 |
合計ジャッジ時間 | 3,937 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
24,072 KB |
testcase_01 | AC | 25 ms
23,892 KB |
testcase_02 | AC | 23 ms
23,436 KB |
testcase_03 | AC | 24 ms
23,724 KB |
testcase_04 | AC | 24 ms
23,460 KB |
testcase_05 | AC | 25 ms
23,412 KB |
testcase_06 | AC | 24 ms
24,048 KB |
testcase_07 | AC | 24 ms
23,412 KB |
testcase_08 | AC | 26 ms
23,472 KB |
testcase_09 | AC | 23 ms
23,592 KB |
testcase_10 | AC | 64 ms
23,568 KB |
testcase_11 | AC | 135 ms
23,664 KB |
testcase_12 | AC | 82 ms
23,904 KB |
testcase_13 | AC | 97 ms
23,856 KB |
testcase_14 | AC | 126 ms
23,724 KB |
testcase_15 | AC | 146 ms
23,664 KB |
testcase_16 | AC | 30 ms
24,408 KB |
testcase_17 | AC | 99 ms
24,408 KB |
testcase_18 | AC | 121 ms
23,880 KB |
testcase_19 | AC | 124 ms
24,060 KB |
testcase_20 | AC | 144 ms
23,712 KB |
testcase_21 | AC | 145 ms
23,892 KB |
testcase_22 | AC | 154 ms
23,664 KB |
testcase_23 | AC | 23 ms
23,556 KB |
ソースコード
#include <cstdio> #include <vector> #include <cstdlib> #include <algorithm> #include <utility> using namespace std; int n; char buf[3000]; vector<vector<int> > cmp; void cmp_swap(int lvl, int a, int b){ if(a < n && b < n){ while((int)cmp.size() <= lvl){ cmp.push_back(vector<int>()); } cmp[lvl].push_back(a); cmp[lvl].push_back(b); } } int oe_merge(int lvl, int lo, int hi, int r){ int step = r * 2; if(step < hi - lo){ int t1 = oe_merge(lvl, lo, hi, step); int t2 = oe_merge(lvl, lo + r, hi, step); int t = max(t1, t2); for(int i = lo + r; i < hi - r; i += step){ cmp_swap(t, i, i + r); } return t + 1; } else{ cmp_swap(lvl, lo, lo + r); return lvl + 1; } } int oe_merge_sort_range(int lvl, int lo, int hi){ if(hi - lo >= 1){ int mid = lo + ((hi - lo) >> 1); int t1 = oe_merge_sort_range(lvl, lo, mid); int t2 = oe_merge_sort_range(lvl, mid + 1, hi); return oe_merge(max(t1, t2), lo, hi, 1); } return lvl; } int main(){ fgets(buf, 3000, stdin); n = strtol(buf, 0, 10); int m = 1; while(m < n){ m <<= 1; } oe_merge_sort_range(0, 0, m - 1); vector<int> v(n); for(int i = 0; i < n; ++i){ v[i] = i + 1; } for(size_t i = 0; i < cmp.size(); ++i){ int len = cmp[i].size(); putchar('?'); for(int j = 0; j < 2 * n; ++j){ if(j < len){ printf(" %d", v[cmp[i][j]]); } else{ printf(" 0"); } } puts(""); fflush(stdout); fgets(buf, 3000, stdin); for(int j = 0; j < len; j += 2){ if(buf[j] == '>'){ swap(v[cmp[i][j]], v[cmp[i][j + 1]]); } } } putchar('!'); for(int i = 0; i < n; ++i){ printf(" %d", v[i]); } puts(""); }