| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 533063 |
2022-03-04T15:25:27 Z |
chaoyue |
Aliens (IOI07_aliens) |
C++17 |
|
1 ms |
200 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, xo, yo, tops, bottoms, lefts, rights, cx, cy, length;
int c, var, m, mm, mmm; //c is constant, var is shiftable coordinate
bool vertical; //whether analysing vertical
bool examine(int a){
string s;
if(vertical){
cout<<"examine "<<xo<<" "<<a<<flush;
}
else{
cout<<"examine "<<a<<" "<<yo<<flush;
}
cin>>s;
if(s == "true") return 1;
return 0;
}
bool query(int x, int y){
string s;
cout<<"examine "<<x<<" "<<y<<flush;
cin>>s;
if(s == "true") return 1;
return 0;
}
void bs(){ //inital binary search
while(1){
m = (c+var)/2;
if(var < c) m++;
if(examine(m)) break;
var = m;
}
}
int getcase(){ //1 -> is first square, 2 -> is second square, 3 -> is third square
mm = (c+m)/2;
mmm = (c+mm)/2;
if(!examine(mm)){
return 2;
}
else{
if(examine(mmm)) return 1;
return 3;
}
}
int bs2(int l, int r){
if(l > r) swap(l, r);
while(r-l > 1){
int mid = (l+r)/2;
if(examine(mid)){
if(var > c){
l = mid;
}
else{
r = mid;
}
}
else{
if(var > c){
r = mid;
}
else{
l = mid;
}
}
}
if(var > c) return l;
return r;
}
int side(int C, int VAR, bool VERTICAL){
int square;
vertical = VERTICAL;
c = C;
var = VAR;
bs();
square = getcase();
if(square == 2){
return bs2(c, mm);
}
else if(square == 1){
return bs2(m, var);
}
else{
return bs2(c, mmm);
}
}
int diag(int hor, int ver){
int newx, newy;
for(int i=1; i<=4; i++){
newx = cx + hor * i * length;
newy = cy + ver * i * length;
if(newx <= 0 || newx > n || newy <= 0 || newy > n || !query(newx, newy)) return i-1;
}
return 4;
}
void solve(){
rights = side(xo, n+1, 0);
lefts = side(xo, 0, 0);
tops = side(yo, n+1, 1);
bottoms = side(yo, 0, 1);
length = rights - lefts + 1;
cx = (lefts + rights)/2;
cy = (bottoms + tops)/2;
int tl, tr, bl, br;
tl = diag(-1, 1);
tr = diag(1, 1);
bl = diag(-1, -1);
br = diag(1, -1);
cx += (br - tl + tr - bl) / 2 * length;
cy += (tl - br + tr - bl) / 2 * length;
cout<<"solution "<<cx<<" "<<cy<<flush;
}
int main(){
cin>>n>>xo>>yo;
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
0 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
200 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
