Submission #400975

#	Time	Username	Problem	Language	Result	Execution time	Memory
400975		peuch	Aliens (IOI07_aliens)	C++17	0 / 100	4 ms	300 KiB

aliens

#include<bits/stdc++.h>
using namespace std;

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

int n;
long long m;
long long inix, iniy;
long long midx, midy;
long long cnt;
long long bordx[4], bordy[4];

map<pair<long long, long long>, int> marc;
map<pair<long long, long long>, int> vist;

void solve(int a, long long b, long long c);
bool query(long long x, long long y);
void getPoint(long long &x, long long &y, int dir);
long long getD(long long x, long long y, int dir);
void bb(long long x, long long y, int dir, long long &ini, long long &fim);
void dfs(long long curx, long long cury);

int main(){
	scanf("%d %lld %lld", &n, &inix, &iniy);
	solve(n, inix, iniy);
	return 0;
}

void solve(int a, long long b, long long c){
	n = a, inix = b, iniy = c;
	for(int i = 0; i < 4; i++){
		getPoint(bordx[i], bordy[i], i);
		midx += bordx[i];
		midy += bordy[i];
	}
	m = bordx[1] - bordx[3] + 1;
//	printf("Got M = %d\n", m);
	midx /= 4;
	midy /= 4;
	dfs(midx, midy);
	midx /= cnt;
	midy /= cnt;
	printf("solution %lld %lld\n", midx, midy);
	fflush(stdout);
}

bool query(long long x, long long y){
	if(x <= 0 || y <= 0 || x > n || y > n) return 0;
	if(marc[make_pair(x, y)] != 0) return marc[make_pair(x, y)] == 1;
	string aux;
	printf("examine %lld %lld\n", x, y);
	fflush(stdout);
	cin >> aux;
	if(aux[0] == 't') marc[make_pair(x, y)] = 1;
	else marc[make_pair(x, y)] = -1;
	return aux[0] == 't';	
}

void getPoint(long long &x, long long &y, int dir){
	long long ini = 0;
	long long fim = getD(inix, iniy, dir) << 1;
	bb(inix, iniy, dir, ini, fim);
	x = inix + ini * dx[dir];
	y = iniy + ini * dy[dir];
//	printf("Got Border %d %d\n", x, y);
}

long long getD(long long x, long long y, int dir){
	long long ret = 0;
	for(int i = 0; i < 31; i++){
		long long vizx = x + (1 << i) * dx[dir];
		long long vizy = y + (1 << i) * dy[dir];
		if(!query(vizx, vizy)) break;
		ret = (1 << i);
	}
	return ret;
}

void bb(long long x, long long y, int dir, long long &ini, long long &fim){
	while(ini != fim){
		long long mid = (ini + fim) >> 1;
		if(ini == fim - 1) mid = fim;
		long long vizx = x + mid * dx[dir];
		long long vizy = y + mid * dy[dir];
		if(!query(vizx, vizy)) fim = mid - 1;
		else ini = mid;
	}
}

void dfs(long long curx, long long cury){
	vist[make_pair(curx, cury)] = 1;
	cnt++;
	for(int i = 0; i < 4; i++){
		long long vizx = curx + 2 * m * dx[i];
		long long vizy = cury + 2 * m * dy[i];
		if(vist[make_pair(vizx, vizy)]) continue;
		if(!query(vizx, vizy)) continue;
		midx += vizx;
		midy += vizy;
		dfs(vizx, vizy);
	}
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d %lld %lld", &n, &inix, &iniy);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10