oj.uz

Submission #310754

# Submission time Handle Problem Language Result Execution time Memory
310754 2020-10-07T19:46:48 Z saarang123 Aliens (IOI07_aliens) C++14
40 / 100
 4 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair

template<class T> bool remin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool remax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int n, m, x, y;
set<array<int, 2>> st;
vector<array<int, 2>> center;

bool qry(int xy, int yx) {
    if(xy > n || yx > n || xy < 1 || yx < 1) return 0;
    cout << "examine " << xy << " " << yx << endl; cout.flush();
    string s; cin >> s;
    return (s == "true" ? 1 : 0);
}

int fst(int a, int b, int dx) {
    int mo = 0;
    while(qry(a, b))
        mo++, a += dx;
    return mo;
}

int snd(int a, int b, int dx) {
    int mo = 0;
    while(qry(a, b))
        mo++, b += dx;
    return mo;
}

void check(int a, int b) {
    if(st.count({a, b})) return;
    if(!qry(a, b)) return;
    st.insert({a, b});
    center.pb({a, b});
    int dx = 2 * m;
    check(a - dx,  b); check(a + dx, b);
    check(a, b - dx); check(a, b + dx);
}

void solve_case() {
    //check dp before greedy, loops, variables in loops, max N values etc.
    int i,j;
    cin >> n >> x >> y;
    array<int, 2> a = {fst(x + 1, y, 1), fst(x - 1, y, -1) };
    array<int, 2> b = {snd(x, y + 1, 1), snd(x, y - 1, -1) };
    array<int, 2> c = { (x + a[0] + x - a[1])/2, (y + b[0] + y - b[1])/2 };
    //for(int o : a) cout << o << " "; cout << endl;
    //for(int o : b) cout << o << " "; cout << endl;
    //for(int o : c) cout << o << " "; cout << endl;
    m = a[0] + 1 + a[1];
    check(c[0], c[1]);
    array<int, 2> ans = {0, 0};
    for(auto ok : center) {
        ans[0] += ok[0]; ans[1] += ok[1];
    }
    //for(auto ok : center) cout << ok[0] << " " << ok[1] << " is a center" << endl;
    //for(int o : ans) cout << o << " "; cout << endl;
    ans[0] /= (int) center.size();
    ans[1] /= (int) center.size();
    cout << "solution ";
    for(int o : ans) cout << o << " "; cout << endl;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    int Testcases = 1;
    //std::cin >> Testcases;
    while(Testcases--) {
        solve_case();
    }
    return 0;
}

Compilation message

aliens.cpp: In function 'void solve_case()':
aliens.cpp:72:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   72 |     for(int o : ans) cout << o << " "; cout << endl;
      |     ^~~
aliens.cpp:72:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |     for(int o : ans) cout << o << " "; cout << endl;
      |                                        ^~~~
aliens.cpp:53:9: warning: unused variable 'i' [-Wunused-variable]
   53 |     int i,j;
      |         ^
aliens.cpp:53:11: warning: unused variable 'j' [-Wunused-variable]
   53 |     int i,j;
      |           ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB too many queries
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB too many queries

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB too many queries
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB too many queries
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB too many queries
2 Halted 0 ms 0 KB -