oj.uz

답안 #293399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293399 2020-09-08T02:21:06 Z Hemimor Aliens (IOI07_aliens) C++14
100 / 100
 3 ms 384 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

// ###############
// ###...###...###
// #####.....#####

ll t=-1,cx,cy;
ll n,x,y,lx,ly,rx,ry;

bool f(ll i,ll j){
	assert(1<=i&&i<=n);
	assert(1<=j&&j<=n);
	cout<<"examine "<<i<<' '<<j<<endl;
	if(t>=0){
		if(cx<=i&&i<cx+5*t&&cy<=j&&j<cy+5*t) return ((i-cx)/t+(j-cy)/t)%2==0;
		return 0;
	}
	string s;
	cin>>s;
	return s=="true";
}

int main(){
//	cin>>t>>cx>>cy;
	cx-=2*t+t/2;
	cy-=2*t+t/2;
	cin>>n>>x>>y;
	ll l=0,r=x;
	while(r-l>1){
		ll m=(l+r)/2;
		if(f(m,y)) r=m;
		else l=m;
	}
	lx=r;
	l=x,r=n+1;
	while(r-l>1){
		ll m=(l+r)/2;
		if(f(m,y)) l=m;
		else r=m;
	}
	rx=r;
	l=0,r=y;
	while(r-l>1){
		ll m=(l+r)/2;
		if(f(x,m)) r=m;
		else l=m;
	}
	ly=r;
	l=y,r=n+1;
	while(r-l>1){
		ll m=(l+r)/2;
		if(f(x,m)) l=m;
		else r=m;
	}
	ry=r;
	if((rx-lx)%5==0&&!f(lx+(rx-lx)/5,y)) rx=lx+(rx-lx)/5;
	if((rx-lx)%3==0&&!f(lx+(rx-lx)/3,y)) rx=lx+(rx-lx)/3;
	if((ry-ly)%5==0&&!f(x,ly+(ry-ly)/5)) ry=ly+(ry-ly)/5;
	if((ry-ly)%3==0&&!f(x,ly+(ry-ly)/3)) ry=ly+(ry-ly)/3;
	ll m=rx-lx;
	assert(m==ry-ly);
	x=(lx+rx)/2,y=(ly+ry)/2;
	ll mx=INF,MX=-INF,my=INF,MY=-INF;
//	cout<<x<<' '<<y<<endl;
	for(int i=-4;i<=4;i++) for(int j=-4;j<=4;j++){
		ll X=x+m*i,Y=y+m*j;
		if(X>=1&&X<=n&&Y>=1&&Y<=n&&f(X,Y)){
			mx=min(mx,X);
			MX=max(MX,X);
			my=min(my,Y);
			MY=max(MY,Y);
		}
	}
	cout<<"solution "<<(mx+MX)/2<<' '<<(my+MY)/2<<endl;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 1 ms 288 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct