結果
問題 | No.2978 Lexicographically Smallest and Largest Subarray |
ユーザー |
|
提出日時 | 2024-12-02 00:10:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 1,103 bytes |
コンパイル時間 | 2,082 ms |
コンパイル使用メモリ | 198,112 KB |
最終ジャッジ日時 | 2025-02-26 10:23:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 57 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; auto ask = [&](int u, int v){ int res; cout << "? " << u + 1 << " " << n << " " << v + 1 << " " << n << endl; cin >> res; return res; }; queue<int> mx, mn; for(int i = 0; i + 1 < n; i += 2){ int rcv = ask(i, i + 1); if(rcv == 1){ mn.emplace(i); mx.emplace(i + 1); }else{ mn.emplace(i + 1); mx.emplace(i); } } while(mn.size() >= 2){ int u = mn.front(); mn.pop(); int v = mn.front(); mn.pop(); if (ask(u, v) == 1) mn.emplace(u); else mn.emplace(v); } while(mx.size() >= 2){ int u = mx.front(); mx.pop(); int v = mx.front(); mx.pop(); if (ask(u, v) == 0) mx.emplace(u); else mx.emplace(v); } cout << "! " << mn.front() + 1 << " " << mn.front() + 1 << " " << mx.front() + 1 << " " << n << endl; }