Submission #742449

#TimeUsernameProblemLanguageResultExecution timeMemory
742449maomao90Worm Worries (BOI18_worm)C++17
44 / 100
34 ms356 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 1000005; int query(int x, int y, int z) { cout << "? " << x << ' ' << y << ' ' << z << endl; int ans; cin >> ans; if (ans == -1) exit(0); return ans; } void guess(int x, int y, int z) { cout << "! " << x << ' ' << y << ' ' << z << endl; exit(0); } int n, m, k, q; namespace st2 { const int MAXN = 1000005; int qry[MAXN]; int fib[MAXN]; int query(int x, int y, int z) { if (x > n) { return 0; } if (qry[x]) { return qry[x]; } cout << "? " << x << ' ' << y << ' ' << z << endl; int ans; cin >> ans; if (ans == -1) exit(0); return qry[x] = ans; } int main() { fib[0] = 1; fib[1] = 2; int gd = -1; REP (i, 2, 50) { fib[i] = fib[i - 1] + fib[i - 2]; if (fib[i] + 1 >= n) { gd = i; break; } } int lo = 1, hi = fib[gd] + 1; int ans = -1; RREP (k, gd, 2) { int mid1 = lo + fib[k - 2], mid2 = lo + fib[k - 1]; assert(hi == lo + fib[k]); cerr << ' ' << mid1 << ' ' << mid2 << '\n'; int l = query(mid1, 1, 1), r = query(mid2, 1, 1); if (l > r) { hi = mid2; } else { lo = mid1; } } assert(lo + 2 == hi); int l = query(lo, 1, 1), m = query(lo + 1, 1, 1), r = query(hi, 1, 1); if (l >= m) { guess(lo, 1, 1); } else if (m >= l && m >= r) { guess(lo + 1, 1, 1); } else { assert(r >= m); guess(hi, 1, 1); } /* int lo = 1, hi = n; while (lo < hi) { int mid = lo + hi + 1 >> 1; int l = query(mid - 1, 1, 1), m = query(mid, 1, 1); if (l < m) { lo = mid; } else { hi = mid - 1; } } guess(lo, 1, 1); */ return 0; } } namespace st3 { const int MAXN = 1005; int qry[MAXN][MAXN]; int fib[MAXN]; int query(int x, int y, int z) { if (x > n || y > m) { return 0; } if (qry[x][y]) { return qry[x][y]; } cout << "? " << x << ' ' << y << ' ' << z << endl; int ans; cin >> ans; if (ans == -1) exit(0); return qry[x][y] = ans; } int main() { int lo = 1, hi = n; int y; while (lo < hi) { int mid = lo + hi + 1 >> 1; int l = 0, r = 0; int mxl, mxr; REP (i, 1, m + 1) { if (mxto(l, query(mid - 1, i, 1))) { mxl = i; } } REP (i, 1, m + 1) { if (mxto(r, query(mid, i, 1))) { mxr = i; } } if (l < r) { lo = mid; y = mxr; } else { hi = mid - 1; y = mxl; } } int x = lo; guess(x, y, 1); return 0; } } int main() { cin >> n >> m >> k >> q; if (m == 1 && k == 1) { st2::main(); } else if (k == 1) { st3::main(); } }

Compilation message (stderr)

worm.cpp: In function 'int st2::main()':
worm.cpp:79:13: warning: unused variable 'ans' [-Wunused-variable]
   79 |         int ans = -1;
      |             ^~~
worm.cpp: In function 'int st3::main()':
worm.cpp:138:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |             int mid = lo + hi + 1 >> 1;
      |                       ~~~~~~~~^~~
worm.cpp:160:14: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |         guess(x, y, 1);
      |         ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...