oj.uz

Submission #400976

# Submission time Handle Problem Language Result Execution time Memory
400976 2021-05-09T00:02:17 Z peuch Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 312 KB 
#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);
	}
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 2 ms 200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 288 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 3 ms 200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 4 ms 304 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 296 KB Output is correct
2 Correct 4 ms 200 KB Output is correct
3 Correct 1 ms 292 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 3 ms 312 KB Output is correct