QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #615626 | #8939. Permutation | m107239 | WA | 3ms | 3660kb | C++23 | 6.3kb | 2024-10-05 19:34:45 | 2024-10-05 19:34:46 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <map>
#include <random>
using ll = long long;
using namespace std;
#ifndef ONLINE_JUDGE
#include "interactlib.hh"
static cave::Interactor _([](auto &test) {
int t = 10;
mt19937_64 rng(random_device{}());
test << t << endl;
while (t--) {
int n = uniform_int_distribution<>(1, 16)(rng);
test << n << endl;
vector<int> a(n);
iota(a.begin(), a.end(), 1);
shuffle(a.begin(), a.end(), rng);
cerr << "Answer: ";
for (int i = 0; i < n; i++) {
cerr << a[i] << " ";
}
cerr << endl;
while (true) {
string op;
test >> op;
if (op == "!") {
int ans;
test >> ans;
if (ans == max_element(a.begin(), a.end()) - a.begin() + 1) {
cerr << "Correct" << endl;
} else {
cerr << "Wrong Answer on test " << t << endl;
}
break;
} else {
int l, r;
test >> l >> r;
int max[2] = {}, idx[2] = {};
for (int i = l - 1; i < r; i++) {
if (a[i] > max[0]) {
max[1] = max[0];
max[0] = a[i];
idx[1] = idx[0];
idx[0] = i;
} else if (a[i] > max[1]) {
max[1] = a[i];
idx[1] = i;
}
}
test << (idx[1] + 1) << endl;
}
}
}
});
#endif
static map<pair<int, int>, int> cache;
static int query(int l, int r) { // use 0-based, right exclusive index internally, but 1-based, right inclusive index externally
if (r - l < 2) {
return -1;
}
auto it = cache.find({l, r});
if (it != cache.end()) {
return it->second;
}
cout << "? " << l + 1 << " " << r << endl;
int x;
cin >> x;
return cache[{l, r}] = x - 1;
}
int solve(int n) {
cache.clear();
int l = 0, r = n;
while (true) {
if (l + 1 == r) {
return l;
}
if (l + 2 == r) {
return l + (l == query(l, r));
}
int m = (l + r) / 2, ml = (l + m) / 2, mr = (m + r) / 2;
int s0 = query(l, r);
if (s0 < ml) {
int s1 = query(l, m);
if (s1 == s0) {
if (l + 1 == m) {
return l;
}
if (l + 2 == m) {
return l + (l == query(l, m));
}
int s2 = query(l, ml);
if (s2 == s0) {
r = ml;
} else {
l = ml;
r = m;
}
} else {
if (m + 1 == r) {
return m;
}
if (m + 2 == r) {
return m + (m == query(m, r));
}
int s2 = query(l, mr);
if (s2 == s0) {
l = m;
r = mr;
} else {
l = mr;
}
}
} else if (s0 < m) {
int s1 = query(l, m);
if (s1 == s0) {
if (l + 1 == m) {
return l;
}
if (l + 2 == m) {
return l + (l == query(l, m));
}
int s2 = query(ml, mr);
if (s2 == s0) {
l = ml;
r = m;
} else {
r = ml;
}
} else {
if (m + 1 == r) {
return m;
}
if (m + 2 == r) {
return m + (m == query(m, r));
}
int s2 = query(ml, mr);
if (s2 == s0) {
l = m;
r = mr;
} else {
l = ml;
}
}
} else if (s0 < mr) {
int s1 = query(m, r);
if (s1 == s0) {
if (m + 1 == r) {
return m;
}
if (m + 2 == r) {
return m + (m == query(m, r));
}
int s2 = query(ml, mr);
if (s2 == s0) {
l = m;
r = mr;
} else {
l = mr;
}
} else {
if (l + 1 == m) {
return l;
}
if (l + 2 == m) {
return l + (l == query(l, r));
}
int s2 = query(ml, mr);
if (s2 == s0) {
l = ml;
r = m;
} else {
r = ml;
}
}
} else {
int s1 = query(m, r);
if (s1 == s0) {
if (m + 1 == r) {
return m;
}
if (m + 2 == r) {
return m + (m == query(m, r));
}
int s2 = query(mr, r);
if (s2 == s0) {
l = mr;
} else {
l = m;
r = mr;
}
} else {
if (l + 1 == m) {
return l;
}
if (l + 2 == m) {
return l + (l == query(l, m));
}
int s2 = query(ml, r);
if (s2 == s0) {
l = ml;
r = m;
} else {
r = ml;
}
}
}
}
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = solve(n) + 1;
cout << "! " << ans << endl;
}
return 0;
}
// [9, 2, 7, 6, 3, 1, 8, 10, 5, 11, 4]
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
3 5 3 3 2 5 6 6 5 6 3 4 3 3
output:
? 1 5 ? 3 5 ? 2 3 ? 4 5 ! 4 ? 1 6 ? 4 6 ? 2 6 ? 2 3 ! 2 ? 1 4 ? 3 4 ! 4
result:
ok Correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3660kb
input:
10000 10 2 2 1 3 5 10 10 10 8 7 10 5 1 5 6 10 4 4 4 4 5 10 10 6 3 2 10 3 3 5 2 10 1 5 5 9 10 10 1 3 1 6 10 2 4 4 9 9 10 3 3 3 3 5 10 4 1 7 4
output:
? 1 10 ? 1 5 ? 1 2 ? 3 5 ? 4 5 ! 4 ? 1 10 ? 6 10 ? 8 10 ? 6 7 ! 6 ? 1 10 ? 1 5 ? 3 7 ? 6 7 ! 7 ? 1 10 ? 1 5 ? 3 7 ? 3 5 ? 4 5 ! 3 ? 1 10 ? 6 10 ? 3 10 ? 1 2 ! 1 ? 1 10 ? 1 5 ? 3 7 ? 1 2 ! 1 ? 1 10 ? 1 5 ? 1 7 ? 8 10 ? 9 10 ! 8 ? 1 10 ? 1 5 ? 1 7 ? 6 7 ! 7 ? 1 10 ? 1 5 ? 1 7 ? 8 10 ? 9 10 ! 10 ? 1 10...
result:
wrong answer Too long queries, n = 10, now length 32 (test case 11)