Submission #117614

#TimeUsernameProblemLanguageResultExecution timeMemory
117614RockyBAliens (IOI07_aliens)C++17
100 / 100
5 ms384 KiB
/// In The Name Of God #include <bits/stdc++.h> #define int long long #define f first #define s second #define pb push_back #define pp pop_back #define mp make_pair #define sz(x) (int)x.size() #define sqr(x) ((x) * 1ll * (x)) #define all(x) x.begin(), x.end() #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define per(i, l, r) for (int i = (l); i >= (r); i--) #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define nl '\n' #define ioi exit(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = (int)5e5 + 7; const int inf = (int)1e9 + 7; const int mod = (int)1e9 + 7; const ll linf = (ll)1e18 + 7; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}; const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; using namespace std; namespace checker { int n, X, Y, m; void init(int _n, int _X, int _Y, int _m) { n = _n, X = _X, Y = _Y, m = _m; } bool check(ll x, ll y) { if (x < X || y < Y) return 0; x = x - X + 1; y = y - Y + 1; x = (x + m - 1) / m; y = (y + m - 1) / m; return x % 2 == y % 2 && x <= 5 && y <= 5; } } ll n; ll cnt; bool check(ll x, ll y) { return 1 <= x && x <= n && 1 <= y && y <= n; } ll ask(ll x, ll y) { if (!check(x, y)) return 0; #ifndef IOI2018 { // --- mine stuf ++cnt; assert(cnt <= 300); } cout << "examine " << x << ' ' << y << endl; string s; cin >> s; return s == "true"; #endif #ifdef IOI2018 { // --- mine stuf ++cnt; } cout << "examine " << x << ' ' << y << endl; return checker :: check(x, y); #endif } pair <int, int> solve() { ll x, y; cin >> n >> x >> y; cnt = 0; ll m = 0; { // --- searching right ll l = 1, r = n, ans = 0; while (l <= r) { ll mid = (l + r) / 2; if (ask(x + mid, y) && ask(x + 2 * mid, y) && ask(x + 3 * mid, y)) ans = mid, l = mid + 1; else r = mid - 1; } ll add = 3 * ans; while (ask(x + add + 1, y)) ++add; ans = add; m += ans; } { // --- searching left ll l = 1, r = n, ans = 0; while (l <= r) { ll mid = (l + r) / 2; if (ask(x - mid, y) && ask(x - 2 * mid, y) && ask(x - 3 * mid, y)) ans = mid, l = mid + 1; else r = mid - 1; } ll add = 3 * ans; while (ask(x - add - 1, y)) ++add; ans = add; x -= ans; m += ans; } ++m; { // --- searching up ll l = 1, r = n, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (ask(x, y + mid) && ask(x, y + 2 * mid) && ask(x, y + 3 * mid)) ans = mid, l = mid + 1; else r = mid - 1; } ll add = 3 * ans; while (ask(x, y + add + 1)) ++add; ans = add; y += ans; } while (ask(x - m, y + m)) x -= m, y += m; while (ask(x - 2 * m, y )) x -= 2 * m; while (ask(x, y + 2 * m)) y += 2 * m; x += m / 2, y -= m / 2; x += 2 * m, y -= 2 * m; cout << "solution " << x << ' ' << y << endl; return {x, y}; } int32_t main() { #ifdef IOI2018 freopen ("in.txt", "r", stdin); //freopen ("case.txt", "w", stdout); #endif //srand(time(0)); checker :: init(25, 1, 1, 5); solve(); ioi ofstream out ("in.txt"); rep(i, 1, 1000) { int _m = 2 * (rand() % 2 + 1) + 1, _n = 5 * _m ; int X = rand() % (_n - 5 * _m + 1) + 1, Y = rand() % (_n - 5 * _m + 1) + 1; checker :: init(_n, X, Y, _m); int sx = rand() % _n + 1, sy = rand() % _n + 1; while (!checker :: check(sx, sy)) { sx = rand() % _n + 1, sy = rand() % _n + 1; } out << _n << ' ' << sx << ' ' << sy << endl; pair <int, int> res = solve(); pair <int, int> center = {X + 2 * _m + _m / 2, Y + 2 * _m + _m / 2}; if (center != res) { cerr << _n << ' ' << _m << ' ' << sx << ' ' << sy << endl; cerr << res.f << ' ' << res.s << endl; cerr << center.f << ' ' << center.s << endl; assert(0); ioi } } //solve(); ioi }
#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...