Submission #106688

#TimeUsernameProblemLanguageResultExecution timeMemory
106688SOIVIEONEAliens (IOI07_aliens)C++14
20 / 100
4 ms412 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define INF 1000000021 #define MOD 1000000007 #define pb push_back #define sqr(a) (a)*(a) #define M(a, b) make_pair(a,b) #define F first #define S second #define all(x) (x.begin(), x.end()) #define deb(x) cerr << #x << " = " << x << '\n' #define N 222222 using namespace std; using namespace __gnu_pbds; typedef long double ld; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; const ld pi = 2 * acos(0.0); template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;} template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;} template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;} //int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; map<pll, bool> mp; ll n, sk = 0; bool ask(ll x, ll y) { if(x <= 0 || x > n || y <= 0 || y > n) return 0; if(mp.count(M(x, y))) return mp[M(x, y)]; sk ++; if(sk > 299) { while(1 > 0) sk ++; } cout << "examine " << x << ' ' << y << '\n'; cout.flush(); string q; cin >> q; return mp[M(x, y)] = (q[0] == 't'); } int main() { ll x, y; cin >> n >> x >> y; ll p = 1; while(p + x <= n && ask(x + p, y)) p *= 2ll; ll l = x + p/2, r = min(x + p, n), hr = l; for(int i = 1; i <= 50; i ++) { ll m = (l + r) >> 1ll; if(ask(m, y)) { l = m + 1; hr = m; } else r = m; } if(ask(hr+1,y)) hr++; p = 1; while(x - p >= 1 && ask(x - p, y)) p *= 2ll; l = max(x - p, 1ll); r = x - p/2; ll hl = r; for(int i = 1; i <= 50; i ++) { ll m = (l + r) >> 1l;; if(!ask(m, y)) { l = m + 1; hl = m; } else r = m; } if(ask(hl, y)==0) hl ++; if(ask(hl-1, y)) hl --; ll mm = hr - hl + 1; p = 1; while(y + p <= n && ask(x, y + p)) p *= 2ll; l = y + p/2; r = min(y + p, n); ll v = l; for(int i = 1; i <= 50; i ++) { ll m = (l + r) >> 1ll; if(ask(x, m)) { l = m + 1; v = m; } else r = m; } if(ask(x, v + 1)) v ++; ll up = v; while(ask(x, up+mm+mm)) up += mm+mm; ll left = hl; while(ask(left-mm-mm, y)) left -= (mm + mm); ll right = left + 5*mm-1; ll down = up - 5*mm+1; cout << "solution " << (left+right)/2ll << ' ' << (up + down)/2ll << '\n'; cout.flush(); return 0; //ios::sync_with_stdio(false); //cin.tie(0); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...