oj.uz

답안 #395028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395028 2021-04-27T16:06:51 Z Nicholas_Patrick 경찰관과 강도 (BOI14_coprobber) C++17
16 / 100
 71 ms 1992 KB 
#include "coprobber.h"
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int sub;
int cop;
bool a[MAX_N][MAX_N];
vector<int> adjLis[MAX_N];
//sub2
int sidelength;
int start(int n, bool A[MAX_N][MAX_N]){
	for(int i=n; i--;)for(int j=n; j--;)
		a[i][j]=A[i][j];
	for(int i=n; i--;)for(int j=n; j--;){
		if(a[i][j])
			adjLis[i].push_back(j);
	}
	sub=0;
	if(sub==0){
		int edge=0;
		for(int i=n; i--;)
			edge+=adjLis[i].size();
		if(edge==n*2-2)
			sub=1;
	}
	if(sub==0){
		int edge=0;
		for(int i=n; i--;)
			edge+=adjLis[i].size();
		edge>>=1;
		for(int i=2; i<n; i++){
			if(n%i or edge!=n*2-i-n/i)
				continue;
			bool can=true;
			for(int j=n/i; j--;)for(int k=i; k--;){
				if(j and not a[j*i+k][(j-1)*i+k])
					can=false;
				if(k and not a[j*i+k][j*i+k-1])
					can=false;
			}
			if(can){
				sidelength=i;
				sub=2;
				break;
			}
		}
	}
	if(sub==0){
		if(n<=100)
			sub=3;
	}
	if(sub==0){
		sub=4;
	}
	if(sub==1){
		return cop=0;
	}
	if(sub==2){
		return cop=0;
	}
	if(sub==3){
		return -1;
		// int unlock[MAX_N][MAX_N];
		// for(int i=n; i--;)for(int j=n; j--;)
		// 	unlock[i][j]=i==j?0:(adjLis[i].size()+1)*adjLis[j].size();
		// vector<int> todo;
		// for(int i=n; i--;)
		// 	todo.push_back(i<<9|i);
		// while(not todo.empty()){
		// 	int x=todo.back();
		// 	todo.pop_back();
		// 	for(int i: adjLis[x>>9])for(int j: adjLis[x&511]){

		// 	}
		// }
		// return cop=0;
	}
	if(sub==4){
		return -1;
		//
	}
}
bool searching(int x, int p, int z){
	if(x==z)
		return true;
	for(int y: adjLis[x]){
		if(y==p)
			continue;
		if(searching(y, x, z))
			return true;
	}
	return false;
}
int nextMove(int r){
	if(sub==1){
		for(int ret: adjLis[cop]){
			if(searching(ret, cop, r)){
				return cop=ret;
			}
		}
	}
	if(sub==2){
		int cx=cop/sidelength, cy=cop%sidelength;
		int rx=r/sidelength, ry=r%sidelength;
		if(rx-cx>ry-cy){
			cx++;
		}else if(rx-cx<ry-cy){
			cy++;
		}
		return cx*sidelength+cy;
	}
}

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 63 ms 1992 KB Output is correct
5 Correct 16 ms 1056 KB Output is correct
6 Correct 71 ms 1728 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Incorrect 1 ms 328 KB the situation repeated
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 1 ms 328 KB the situation repeated
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 63 ms 1992 KB Output is correct
5 Correct 16 ms 1056 KB Output is correct
6 Correct 71 ms 1728 KB Output is correct
7 Correct 0 ms 200 KB Output is correct
8 Incorrect 1 ms 328 KB the situation repeated
9 Halted 0 ms 0 KB -