| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157359 |
2019-10-11T03:17:51 Z |
my99n |
Aliens (IOI07_aliens) |
C++14 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
// #include"alienslib.h"
// #include "alienslib.cpp"
int examine(int x, int y) {
string res;
cout << "examine " << x << ' ' << y << endl;
cin >> res;
return res == "true";
}
void solution (int x, int y) {
cout << "solution " << x << ' ' << y << endl;
}
void get_size_and_start(int &N, int &X0, int &Y0){
scanf("%d %d %d", &N, &X0, &Y0);
}
using namespace std;
int n;
int bsearch (bool axis, bool high, int l, int r, int st){
if (l == r) return l;
if (high) {
if (axis) {
int mid = (l+r+1)/2;
int res = examine(mid, st);
assert(res != -1);
if (res) return bsearch(axis, high, mid, r, st);
else return bsearch(axis, high, l, mid-1, st);
}
else {
int mid = (l+r+1)/2;
int res = examine(st, mid);
assert(res != -1);
if (res) return bsearch(axis, high, mid, r, st);
else return bsearch(axis, high, l, mid-1, st);
}
}
else {
if (axis) {
int mid = (l+r)/2;
int res = examine(mid, st);
assert(res != -1);
if (res) return bsearch(axis, high, l, mid, st);
else return bsearch(axis, high, mid+1, r, st);
}
else {
int mid = (l+r)/2;
int res = examine(st, mid);
assert(res != -1);
if (res) return bsearch(axis, high, l, mid, st);
else return bsearch(axis, high, mid+1, r, st);
}
}
return -1;
}
int bound (bool axis, bool high, int x, int y, int a = 1) {
// if axis == 1, y must be static and vice versa
if (x > n) return n;
if (x <= 0) return 0;
if (high) {
// operator +
if (axis) {
int res = examine(x+a, y);
assert(res != -1);
if (res) return bound(axis, high, x+a, y, a<<1);
else return bsearch(axis, high, x, x+a, y);
}
else {
int res = examine(x, y+a);
assert(res != -1);
if (res) return bound(axis, high, x, y+a, a<<1);
else return bsearch(axis, high, y, y+a, x);
}
}
else {
// operator -
if (axis) {
int res = examine(x-a, y);
assert(res != -1);
if (res) return bound(axis, high, x-a, y, a<<1);
else return bsearch(axis, high, x-a, x, y);
}
else {
int res = examine(x, y-a);
assert(res != -1);
if (res) return bound(axis, high, x, y-a, a<<1);
else return bsearch(axis, high, y-a, y, x);
}
}
return -1;
}
int main(){
int x, y;
get_size_and_start(n, x, y);
int xh = bound(1, 1, x, y);
int yh = bound(0, 1, x, y);
int xl = bound(1, 0, x, y);
int yl = bound(0, 0, x, y);
int xc = (xh+xl+1)/2;
int yc = (yh+yl+1)/2;
// cerr << xc << ' ' << yc << endl;
int size = xh-xl+1;
assert(size == yh-yl+1);
vector<pair<int,int>> around, twostep;
for(int i = -1; i <= 1; i+=2){
for(int j = -1; j <= 1; j+=2){
if (examine(xc+i*size, yc+j*size) == 1) around.push_back({i, j});
if (examine(xc+i*size*2, yc+j*size*2)) twostep.push_back({i, j});
}
}
if (around.size() == 1) {
solution(xc+around[0].first*size*2, yc+around[0].second*size*2);
return 0;
}
if (around.size() == 2) {
if (around[0].first == around[1].first) {
solution(xc+around[0].first*2*size, yc);
return 0;
}
if (around[0].second == around[1].second) {
solution(xc,around[0].second*2*size+yc);
return 0;
}
}
if (twostep.size() == 1) {
solution(xc+twostep[0].first*size, yc+twostep[0].second*size);
return 0;
}
else {
solution(xc, yc);
return 0;
}
assert(false);
return 0;
}
Compilation message
aliens.cpp: In function 'int examine(int, int)':
aliens.cpp:6:5: error: 'string' was not declared in this scope
string res;
^~~~~~
aliens.cpp:6:5: note: suggested alternatives:
In file included from /usr/include/c++/7/iosfwd:39:0,
from /usr/include/c++/7/ios:38,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from aliens.cpp:1:
/usr/include/c++/7/bits/stringfwd.h:74:33: note: 'std::__cxx11::string'
typedef basic_string<char> string;
^~~~~~
/usr/include/c++/7/bits/stringfwd.h:74:33: note: 'std::__cxx11::string'
aliens.cpp:7:5: error: 'cout' was not declared in this scope
cout << "examine " << x << ' ' << y << endl;
^~~~
aliens.cpp:7:5: note: suggested alternative:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:75:0,
from aliens.cpp:1:
/usr/include/c++/7/iostream:61:18: note: 'std::cout'
extern ostream cout; /// Linked to standard output
^~~~
aliens.cpp:7:44: error: 'endl' was not declared in this scope
cout << "examine " << x << ' ' << y << endl;
^~~~
aliens.cpp:7:44: note: suggested alternative:
In file included from /usr/include/c++/7/istream:39:0,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from aliens.cpp:1:
/usr/include/c++/7/ostream:590:5: note: 'std::endl'
endl(basic_ostream<_CharT, _Traits>& __os)
^~~~
aliens.cpp:8:5: error: 'cin' was not declared in this scope
cin >> res;
^~~
aliens.cpp:8:5: note: suggested alternative:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:75:0,
from aliens.cpp:1:
/usr/include/c++/7/iostream:60:18: note: 'std::cin'
extern istream cin; /// Linked to standard input
^~~
aliens.cpp:8:12: error: 'res' was not declared in this scope
cin >> res;
^~~
aliens.cpp: In function 'void solution(int, int)':
aliens.cpp:12:5: error: 'cout' was not declared in this scope
cout << "solution " << x << ' ' << y << endl;
^~~~
aliens.cpp:12:5: note: suggested alternative:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:75:0,
from aliens.cpp:1:
/usr/include/c++/7/iostream:61:18: note: 'std::cout'
extern ostream cout; /// Linked to standard output
^~~~
aliens.cpp:12:45: error: 'endl' was not declared in this scope
cout << "solution " << x << ' ' << y << endl;
^~~~
aliens.cpp:12:45: note: suggested alternative:
In file included from /usr/include/c++/7/istream:39:0,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from aliens.cpp:1:
/usr/include/c++/7/ostream:590:5: note: 'std::endl'
endl(basic_ostream<_CharT, _Traits>& __os)
^~~~
aliens.cpp: In function 'void get_size_and_start(int&, int&, int&)':
aliens.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &X0, &Y0);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
