Submission #133660

#	Time	Username	Problem	Language	Result	Execution time	Memory
133660		Vlatko	Cezar (COCI16_cezar)	C++14	0 / 100	3 ms	380 KiB

cezar

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int A = 26;
const int maxn = 105;

int n;
int order[maxn];
string words[maxn];
char mapped[256];
char invmapped[256];

bool map_after(char ch, char &mp, char mp_other) {
	for (char ch2 = mp_other+1; ch2 <= 'z'; ++ch2) {
		if (invmapped[ch2] == '$') {
			mp = ch2;
			invmapped[mp] = ch;
			// cout << "map_after, ch=" << ch << ", mp_other=" << mp_other << " ==> mp=" << mp << "\n";
			return true;
		}
	}
	return false;
}

bool map_before(char ch, char &mp, char mp_other) {
	for (char ch2 = 'a'; ch2 < mp_other; ++ch2) {
		if (invmapped[ch2] == '$') {
			mp = ch2;
			invmapped[mp] = ch;
			// cout << "map_before, ch=" << ch << ", mp_other=" << mp_other << " ==> mp=" << mp << "\n";
			return true;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> words[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> order[i];
		--order[i];
	}
	for (int i = 0; i < 256; ++i) {
		mapped[i] = invmapped[i] = '$';
	}
	for (int oid = 0; oid+1 < n; ++oid) {
		int w1 = order[oid], w2 = order[oid+1];
		int n1 = words[w1].length(), n2 = words[w2].length();
		bool lexi_smaller = false;
		// cout << "oid=" << oid << " w1=" << w1 << " w2=" << w2 << endl;
		for (int i = 0; i < min(n1, n2); ++i) {
			char &ch1 = words[w1][i], &ch2 = words[w2][i];
			char &mp1 = mapped[ch1], &mp2 = mapped[ch2];
			// cout << "i=" << i << "\n";
			if (ch1 == ch2) {

			} else if (mp1 != '$' && mp2 != '$') {
				if (mp1 > mp2) {
					cout << "NE\n";
					return 0;
				} else { // w1 < w2
					lexi_smaller = true;
					break;
				}
			} else if (mp1 != '$' && mp2 == '$') {
				if (!map_after(ch2, mp2, mp1)) {
					cout << "NE\n";
					return 0;
				}
				lexi_smaller = true;
				break;
			} else if (mp1 == '$' && mp2 != '$') {
				if (!map_before(ch1, mp1, mp2)) {
					cout << "NE\n";
					return 0;
				}
				lexi_smaller = true;
				break;
			} else {
				// both unset
				map_after(ch1, mp1, 'a'-1);
				if (!map_after(ch2, mp2, mp1)) {
					cout << "NE\n";
					return 0;
				}
				lexi_smaller = true;
				break;
			}
		}
		if (lexi_smaller == false) {
			if (n1 == n2) { // lexicographically equal
			
			} else { // n1 > n2, but common prefix is equal, so w2 is prefix of w1
				cout << "NE\n";
				return 0;
			}
		}
	}
	cout << "DA\n";
	for (char ch = 'a'; ch <= 'z'; ++ch) {
		if (mapped[ch] == '$') {
			map_after(ch, mapped[ch], 'a'-1);
		}
		cout << mapped[ch];
		// cout << endl;
	}
	cout << "\n";
}

Compilation message (stderr)

cezar.cpp: In function 'bool map_after(char, char&, char)':
cezar.cpp:17:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (invmapped[ch2] == '$') {
                    ^
cezar.cpp:19:16: warning: array subscript has type 'char' [-Wchar-subscripts]
    invmapped[mp] = ch;
                ^
cezar.cpp: In function 'bool map_before(char, char&, char)':
cezar.cpp:29:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (invmapped[ch2] == '$') {
                    ^
cezar.cpp:31:16: warning: array subscript has type 'char' [-Wchar-subscripts]
    invmapped[mp] = ch;
                ^
cezar.cpp: In function 'int main()':
cezar.cpp:59:26: warning: array subscript has type 'char' [-Wchar-subscripts]
    char &mp1 = mapped[ch1], &mp2 = mapped[ch2];
                          ^
cezar.cpp:59:46: warning: array subscript has type 'char' [-Wchar-subscripts]
    char &mp1 = mapped[ch1], &mp2 = mapped[ch2];
                                              ^
cezar.cpp:107:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (mapped[ch] == '$') {
                ^
cezar.cpp:108:27: warning: array subscript has type 'char' [-Wchar-subscripts]
    map_after(ch, mapped[ch], 'a'-1);
                           ^
cezar.cpp:110:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   cout << mapped[ch];
                    ^

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