oj.uz

Submission #758455

# Submission time Handle Problem Language Result Execution time Memory
758455 2023-06-14T16:04:52 Z rshohruh Aliens (IOI07_aliens) C++17
60 / 100
 2 ms 336 KB 
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1e9+7;
const int MAXN = 2e5;
const int inf = 1e9;
double eps = 1e-5;
#define endl "\n"
#define dbg(x) cerr<<#x<<" = "<<x<<endl

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

// #define with_testcases

ll n;
bool query(ll x, ll y){
    if(x > n || x <= 0 || y > n || y <= 0) return false;
    cout << "examine " << x << ' ' << y << endl;
    string s;
    cin >> s;
    return (s == "true" ? true : false);
}

void answer(ll x, ll y){
    cout << "solution " << x << ' ' << y << endl;
    exit(0);
}

void t_main(){
    ll u, v;
    cin >> n >> u >> v;
    ll l = 1, r = v;
    while(l != r){
        ll m = (l+r)>>1;
        if(query(u, m)) r=m;
        else l=m+1;
    }
    ll v1 = l;
    dbg(v1);
    l = v, r = n;
    while(l != r){
        ll m = (l+r+1)>>1;
        if(query(u, m)) l = m;
        else r = m-1;
    } 
    ll v2 = l;
    dbg(v2);
    ll m;
    if(!query(u, v1+(v2-v1)/2)){
        m = (v2-v1+1)/3;
    } else {
        if(query(u, v1+(v2-v1)/5)){
            m = (v2-v1+1)/5;
        } else {
            m = (v2-v1+1);
        }
    }
    ll V = v2;
    dbg(m);
    dbg(V);
    l = u, r = u+m;
    while(l != r){
        ll m = (l+r+1)>>1;
        if(query(m, V)) l = m;
        else r = m-1;
    }
    ll U = l;
    dbg(U);
    U = U - m/2;
    V = V - m/2;
    while(query(U-m, V-m)) U -= m, V -= m;
    while(query(U-2*m, V)) U -= 2*m;
    while(query(U, V-2*m)) V -= 2*m;
    answer(U+2*m, V+2*m);
}

signed main(){
    signed t = 1;
    // cin.tie(nullptr)->sync_with_stdio(false);
    #ifdef with_testcases
        cin >> t;
    #endif
    while(t--){
        t_main();
        cout << '\n';
    }
    return 0;
}


/*
 _____   _____ _    _  ____  _    _ _____  _    _ _    _ 
|  __ \ / ____| |  | |/ __ \| |  | |  __ \| |  | | |  | |
| |__) | (___ | |__| | |  | | |__| | |__) | |  | | |__| |
|  _  / \___ \|  __  | |  | |  __  |  _  /| |  | |  __  |
| | \ \ ____) | |  | | |__| | |  | | | \ \| |__| | |  | |
|_|  \_\_____/|_|  |_|\____/|_|  |_|_|  \_\____ /|_|  |_|
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 304 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 1 ms 296 KB Incorrect
4 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct