Submission #1153824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153824		YSH2020	Vlak (COCI20_vlak)	C++20	70 / 70	9 ms	1208 KiB

Main

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

vector<string> a;
vector<string> b;

int solve(int a_s, int a_e, int b_s, int b_e, int c, int m) {
  //currently at the cth character, and its m's turn to play.
  //categorise by first letter.
  vector<int> ranges[26];
  for (int i = a_s; i <= a_e; i++) {
    if (a[i].size() > c) ranges[(int)(a[i][c]-'a')].push_back(i);
  }
  vector<int> ranges2[26];
  for (int i = b_s; i <= b_e; i++) {
    if (b[i].size() > c) ranges2[(int)(b[i][c]-'a')].push_back(i);
  }
  if (m == 0) {
    //player a to play
    for (int i = 0; i < 26; i++) {
      if (ranges[i].size() > 0 and ranges2[i].size() == 0) {
        return 0;
      }
      if (ranges[i].size() == 0) continue;
      if (solve(ranges[i][0], ranges[i][ranges[i].size()-1], ranges2[i][0], ranges2[i][ranges2[i].size()-1], c+1, 1-m) == 0) {
        return 0;
      }
    }
    return 1;
  }
  else {
    for (int i = 0; i < 26; i++) {
      if (ranges2[i].size() > 0 and ranges[i].size() == 0) return 1;
      if (ranges2[i].size() == 0) continue;
      if (solve(ranges[i][0], ranges[i][ranges[i].size()-1], ranges2[i][0], ranges2[i][ranges2[i].size()-1], c+1, 1-m) == 1) return 1;
    }
    return 0;
  }
}



int main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    string s; cin >> s;
    a.push_back(s);
  }
  int m ;cin >> m;
  for (int i = 0; i < m; i++) {
    string s; cin >> s;
    b.push_back(s);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  if (solve(0, n-1, 0, m-1, 0, 0) == 0) cout << "Nina";
  else cout << "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