oj.uz

Submission #400964

# Submission time Handle Problem Language Result Execution time Memory
400964 2021-05-08T22:35:52 Z peuch Aliens (IOI07_aliens) C++17
0 / 100
 4 ms 200 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];

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

Compilation message

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

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 200 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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