제출 #282616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282616		shivensinha4	경찰관과 강도 (BOI14_coprobber)	C++17	100 / 100	1475 ms	54688 KiB

coprobber

#include <bits/stdc++.h> 
#include "coprobber.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'

int posc;
//const int MAX_N = 500;
vi choice[MAX_N+1][MAX_N+1][3];

int start(int N, bool A[MAX_N][MAX_N]) {
	int ct[MAX_N+1][MAX_N+1][3], win[MAX_N+1][MAX_N+1][3];
	
	vi deg(N);
	for_(i, 0, N) for_(j, 0, N) if (A[i][j]) deg[i] += 1;
	queue<vi> q; // {0, 0, 0 -> cop / 1 -> robber}
	for_(i, 0, N) {
		win[i][i][0] = win[i][i][1] = true;
		q.push({i, i, 0});
		q.push({i, i, 1});
	}
	
	while (q.size()) {
		vi curr = q.front(); q.pop();
		if (curr[2] == 0) {
			for_(i, 0, N) if (A[i][curr[1]] and !win[curr[0]][i][1]) {
				ct[curr[0]][i][1] += 1;
				if (ct[curr[0]][i][1] == deg[i]) {
					win[curr[0]][i][1] = true;
					choice[curr[0]][i][1] = curr;
					q.push({curr[0], i, 1});
				}
			}
		} else {
			for_(i, 0, N) if ((A[i][curr[0]] or i == curr[0]) and !win[i][curr[1]][0]) {
				win[i][curr[1]][0] = true;
				choice[i][curr[1]][0] = curr;
				q.push({i, curr[1], 0});
			}
		}
	}
	
	posc = -1;
	for_(i, 0, N) {
		int c = 0;
		for_(j, 0, N) c += win[i][j][0];
		if (c == N) {
			posc = i;
			//cout << "can start at " << i << endl;
		}
	}
	
    return posc;
}

int nextMove(int R) {
	//cout << posc << " " << R << endl;
	posc = choice[posc][R][0][0];
	return posc;
}


//int main() {
	//#ifndef ONLINE_JUDGE
	//freopen("test.in", "r", stdin);
	//#endif
	
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	//bool A[MAX_N][MAX_N] = {{0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}};
	//cout << start(4, A) << endl;
	//cout << nextMove(1) << endl;
	//cout << nextMove(0) << endl;

	//return 0;
//}

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40