제출 #400976

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

int xi, yi, mi;

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

bool answer(int a, int b){
	int xDist = abs(a - xi);
	int yDist = abs(b - yi);
	if(xDist <= mi / 2 && yDist <= mi / 2) return true;
	if(xDist <= mi / 2 && yDist > 3 * mi / 2 && yDist <= 5 * mi / 2) return true;
	if(xDist > mi / 2 && xDist <= 3 * mi / 2 && yDist > mi / 2 && yDist <= 3 * mi / 2) return true;
	if(yDist <= mi / 2 && xDist > 3 * mi / 2 && xDist <= 5 * mi / 2) return true;
	if(xDist > 3 * mi / 2 && xDist <= 5 * mi / 2 && yDist > 3 * mi / 2 && yDist <= 5 * mi / 2) return true;
	return false;
}

int main(){
	scanf("%d %lld %lld", &n, &inix, &iniy);
//	scanf("%d %d %d %d %d %d", &n, &mi, &inix, &iniy, &xi, &yi);
	solve(n, inix, iniy);
//	if(midx == xi && midy == yi) printf("Correct.\n");
//	else printf("Incorrect.\n");
	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);
//		printf("Borda: %d %d\n", bordx[i], bordy[i]);
	}
	m = bordx[1] - bordx[3] + 1;
	midx = (bordx[1] + bordx[3]) / 2;
	midy = (bordy[0] + bordy[2]) / 2;
//	printf("Mid = %d %d\n", midx, midy);
	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;
	if(verbose) printf("examine %lld %lld\n", x, y);
	else{
		if(answer(x, y)) aux[0] = 't';
		else aux[0] = 'f';
	}
	fflush(stdout);
	if(verbose) 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];
}

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:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d %lld %lld", &n, &inix, &iniy);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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