제출 #1154248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154248		jmuzhen	Vlak (COCI20_vlak)	C++20	70 / 70	94 ms	14660 KiB

Main

#include<bits/stdc++.h>
using namespace std;

vector<string> N, E;
map<string, bool> prefixN, prefixE;
int n, m;

void init_prefixes() {
	for (auto s : N) {
		string prefix;
		for (int i = 0; i < s.length(); i++) {
			prefix += s[i];
			prefixN[prefix]=1;
		}
	}
	for (auto s : E) {
		string prefix;
		for (int i = 0; i < s.length(); i++) {
			prefix += s[i];
			prefixE[prefix]=1;
		}
	}
}

auto& get_prefix_map(int turn) {
	return turn == 1 ? prefixN : prefixE;
}

// returns value from current player's pov.
int search(string& a, int depth, int turn) {
	// check for win/loss
	// if we don't have this prefix, then we've lost
	if (!a.empty() && get_prefix_map(turn).count(a) == 0) {
		return -1;
	}

	int bestValue = -1;
	// note that we implicitly return -1 (loss) if we have no legal moves.

	// move generation
	for (char c = 'a'; c <= 'z'; c++) {
		// make move
		a += c;

		// check legality
		if (get_prefix_map(turn).count(a) == 0) {
			// undo move and continue
			a.pop_back();
			continue;
		}

		// search again
		int score = -search(a, depth+1, 1 - turn);
		bestValue = max(bestValue, score);
		
		// undo move
		a.pop_back();
	}

	return bestValue;
	
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string x;cin>>x;N.push_back(x);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		string x;cin>>x;E.push_back(x);
	}

	init_prefixes();

	int score = search(*new string(), 0, 1);

	cout << (score == 1 ? "Nina" : "Emilija");
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10