Skip to content

Instantly share code, notes, and snippets.

@koosaga
Created Jan 1, 2023
Embed
What would you like to do?
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using llf = long double;
using pi = array<int, 2>;
// Let a matrix be monotone if Opt(i) <= Opt(i + 1) for all rows i.
// Given a totally monotone matrix (where every 2x2 submatrix is monotone), find the list of row optima positions.
// Need to implement select(r, u, v): checks if v is "better" solution than u.
// Ex) if we are finding a maximum, select(r, u, v) = (f(r, u) <= f(r, v)) since it makes v better.
map<pi, int> mp;
int f(int u, int v) {
if (mp.count({u, v}))
return mp[{u, v}];
cout << "? " << u + 1 << " " << v + 1 << endl;
int x;
cin >> x;
return mp[{u, v}] = x;
}
bool select(int r, int u, int v) {
assert(u < v);
return f(r, u) > f(r, v);
}
vector<int> recurse(vector<int> &rw, vector<int> &cl) {
if (sz(rw) == 1) {
vector<int> opt = {0};
for (int i = 1; i < sz(cl); i++) {
if (select(rw[0], cl[opt[0]], cl[i]))
opt[0] = i;
}
return opt;
}
vector<int> stk, rev;
for (int i = 0; i < sz(cl); i++) {
while (sz(stk) && select(rw[sz(stk) - 1], stk.back(), cl[i])) {
stk.pop_back();
rev.pop_back();
}
if (sz(stk) < sz(rw)) {
stk.push_back(cl[i]);
rev.push_back(i);
}
}
vector<int> half;
for (int i = 0; i < sz(rw); i += 2) {
half.push_back(rw[i]);
}
vector<int> ans(sz(rw));
auto interp = recurse(half, stk);
for (int i = 0; i < sz(interp); i++)
ans[2 * i] = interp[i];
for (int i = 1; i < sz(ans); i += 2) {
int s = ans[i - 1];
int e = (i + 1 < sz(ans) ? ans[i + 1] : sz(stk) - 1);
ans[i] = s;
for (int j = s + 1; j <= e; j++) {
if (select(rw[i], stk[ans[i]], stk[j]))
ans[i] = j;
}
}
for (int i = 0; i < sz(ans); i++)
ans[i] = rev[ans[i]];
return ans;
}
vector<int> smawk(int n, int m) {
assert(n >= 1 && m >= 1);
vector<int> rw(n), cl(m);
iota(all(rw), 0);
iota(all(cl), 0);
return recurse(rw, cl);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
auto ans = smawk(n, m);
int dap = 1e9;
for (int i = 0; i < n; i++) {
dap = min(dap, f(i, ans[i]));
}
cout << "! " << dap << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment