제출 #400964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400964		peuch	Aliens (IOI07_aliens)	C++17	0 / 100	4 ms	200 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;

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);
	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;
	midx /= 4;
	midy /= 4;
	dfs(midx, midy);
	midx /= cnt;
	midy /= cnt;
	printf("solution %lld %lld\n", midx, midy);
	fflush(stdout);
	return 0;
}

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;
	printf("examine %lld %lld\n", x, y);
	fflush(stdout);
	string aux;
	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);
	bb(inix, iniy, dir, ini, fim);
	x = inix + ini * dx[dir];
	y = iniy + ini * dy[dir];
}

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);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'int main()':
aliens.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  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