結果
問題 | No.2978 Lexicographically Smallest and Largest Subarray |
ユーザー |
![]() |
提出日時 | 2024-12-16 22:10:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 2,215 bytes |
コンパイル時間 | 1,634 ms |
コンパイル使用メモリ | 119,560 KB |
実行使用メモリ | 25,476 KB |
平均クエリ数 | 1499.00 |
最終ジャッジ日時 | 2024-12-16 22:10:30 |
合計ジャッジ時間 | 16,099 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 57 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <set> #include <queue> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i< (int)(n); i++) int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; cin >> n >> q; set<int> high, low; for(int i=1; i+1<=n; i+=2){ cout << "? " << i << " " << i << " " << i+1 << " " << i+1 << endl; int j; cin >> j; if(j == -1){ return 0; } if(j == 1){ high.insert(i+1); low.insert(i); }else{ high.insert(i); low.insert(i+1); } } if(n % 2 != 0){ high.insert(n); low.insert(n); } while(low.size() > 1){ queue<int> que; while(low.size() > 0){ que.push(*low.begin()); low.erase(*low.begin()); } while(que.size() > 1){ int a = que.front(); que.pop(); int b = que.front(); que.pop(); cout << "? " << a << " " << a << " " << b << " " << b << endl; int j; cin >> j; if(j == -1){ return 0; } if(j == 0){ low.insert(b); }else{ low.insert(a); } } while(!que.empty()){ low.insert(que.front()); que.pop(); } } while(high.size() > 1){ queue<int> que; while(high.size() > 0){ que.push(*high.begin()); high.erase(*high.begin()); } while(que.size() > 1){ int a = que.front(); que.pop(); int b = que.front(); que.pop(); cout << "? " << a << " " << n << " " << b << " " << n << endl; int j; cin >> j; if(j == -1){ return 0; } if(j == 0){ high.insert(a); }else{ high.insert(b); } } while(!que.empty()){ high.insert(que.front()); que.pop(); } } cout << "! " << *low.begin() << " " << *low.begin() << " " << *high.begin() << " " << n << endl; return 0; }