# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
161510 |
2019-11-02T19:04:34 Z |
sans |
Aliens (IOI07_aliens) |
C++14 |
|
5 ms |
380 KB |
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(int yy = 0; yy < YY; ++yy)
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> ii;
const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
int deviceUsed = 300;
int N, X0, Y0;
map<ii, int> isred;
bool device(int x, int y)
{
if(x < 1 or x > N or y < 1 or y > N) return false;
if(isred[mp(x, y)]) return (isred[mp(x, y)] == 1 ? true : false);
if(!deviceUsed) return false;
cout << "examine " << x << sp << y << endl;
cout.flush();
string answer;
cin >> answer;
deviceUsed--;
bool res = (answer == "true");
isred[mp(x, y)] = (res ? 1 : -1);
return res;
}
int main(int argc, char **argv)
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> X0 >> Y0;
isred[mp(X0, Y0)] = 1;
int XR, XL, YB, YU, M;
int high, low, k = 1;
while(true)
{
if(device(X0 + k, Y0)){ k *= 2; }
else{ high = k; low = k / 2; break; }
}
while(high - low > 1)
{
int mid = (high + low) / 2;
if(device(X0 + mid, Y0)) low = mid;
else high = mid;
}
XR = X0 + low;
k = 1;
while(true)
{
if(device(X0 - k, Y0)){ k *= 2; }
else{ high = k; low = k/2; break; }
}
while(high - low > 1)
{
int mid = (high + low) / 2;
if(device(X0 - mid, Y0)) low = mid;
else high = mid;
}
XL = X0 - low;
M = XR - XL + 1;
k = 1;
while(true)
{
if(device(X0, Y0 - k)){ k *= 2; }
else{ high = k; low = k/2; break; }
}
while(high - low > 1)
{
int mid = (high + low) / 2;
if(device(X0, Y0 - mid)) low = mid;
else high = mid;
}
YB = Y0 - low;
YU = YB + M - 1;
int XC = XL + M/2, YC = YB + M/2;
int cevapX, cevapY;
if( device(XC + 2*M, YC) and device(XC + 4*M, YC) )
{
if( device(XC, YC + 2*M) and device(XC, YC + 4*M) )
cevapX = XC + 2*M, cevapY = YC + 2*M;
else if( device(XC, YC + 2*M) and device(XC, YC - 2*M) )
cevapX = XC + 2*M, cevapY = YC;
else if( device(XC, YC - 2*M) and device(XC, YC - 4*M) )
cevapX = XC + 2*M, cevapY = YC - 2*M;
}
else if( device(XC - 2*M, YC) and device(XC - 4*M, YC) )
{
if( device(XC, YC + 2*M) and device(XC, YC + 4*M) )
cevapX = XC - 2*M, cevapY = YC + 2*M;
else if( device(XC, YC - 2*M) and device(XC, YC + 2*M) )
cevapX = XC - 2*M, cevapY = YC;
else if( device(XC, YC - 4*M) and device(XC, YC - 2*M) )
cevapX = XC - 2*M, cevapY = YC - 2*M;
}
else if( device(XC - 2*M, YC) and device(XC + 2*M, YC) )
{
if(device(XC, YC - 2*M) and device(XC, YC - 4*M))
cevapX = XC, cevapY = YC-2*M;
else if(device(XC, YC - 2*M) and device(XC, YC + 2*M))
cevapX = XC, cevapY = YC;
else if(device(XC, YC + 2*M) and device(XC, YC + 4*M))
cevapX = XC, cevapY = YC + 2*M;
}
else
{
if( device(XC - 2*M, YC) and device(XC, YC + 2*M) )
cevapX = XC - M, cevapY = YC + M;
else if( device(XC - 2*M, YC) and device(XC, YC - 2*M) )
cevapX = XC - M, cevapY = YC - M;
else if( device(XC + 2*M, YC) and device(XC, YC + 2*M) )
cevapX = XC + M, cevapY = YC + M;
else if( device(XC + 2*M, YC) and device(XC, YC - 2*M) )
cevapX = XC + M, cevapY = YC - M;
}
cout << "solution " << cevapX << sp << cevapY << endl;
return 0;
}
//cikisir
Compilation message
aliens.cpp: In function 'int main(int, char**)':
aliens.cpp:52:21: warning: variable 'YU' set but not used [-Wunused-but-set-variable]
int XR, XL, YB, YU, M;
^~
aliens.cpp:5:14: warning: 'cevapY' may be used uninitialized in this function [-Wmaybe-uninitialized]
#define endl '\n'
^~~~
aliens.cpp:103:17: note: 'cevapY' was declared here
int cevapX, cevapY;
^~~~~~
aliens.cpp:4:12: warning: 'cevapX' may be used uninitialized in this function [-Wmaybe-uninitialized]
#define sp ' '
^~~
aliens.cpp:103:9: note: 'cevapX' was declared here
int cevapX, cevapY;
^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
4 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
248 KB |
Output is correct |
3 |
Correct |
4 ms |
376 KB |
Output is correct |