Submission #742429

#TimeUsernameProblemLanguageResultExecution timeMemory
742429maomao90Worm Worries (BOI18_worm)C++17
0 / 100
1 ms464 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[50]; 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; while (ans == -1) { x++; } 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]; while (hi != lo + fib[k]) { ans++; } 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; } } while (hi != lo + 2) { ans++; } 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; } } int main() { cin >> n >> m >> k >> q; if (m == 1 && k == 1) { st2::main(); } }
#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...