Submission #705638

#	Time	Username	Problem	Language	Result	Execution time	Memory
705638		stevancv	Three Friends (BOI14_friends)	C++14	100 / 100	69 ms	32912 KiB

friends

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e6 + 5;
const int inf = 2e9;
const int mod = 1e9 + 7;
int a[N], prv[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> p(26);
    for (int i = 0; i < n; i++) {
        if (!p[s[i] - 'A'].empty()) prv[i] = p[s[i] - 'A'].back();
        else prv[i] = -1;
        p[s[i] - 'A'].push_back(i);
    }
    int odd = 0;
    for (int i = 0; i < 26; i++) {
        odd += p[i].size() % 2;
    }
    if (odd != 1) {
        cout << "NOT POSSIBLE" << en;
        return 0;
    }
    int who = -1;
    int good = 0;
    for (int i = 0; i < 26; i++) {
        int y = p[i].size() / 2;
        for (int j = 0; j < y; j++) {
            a[p[i][j]] = p[i][j + y];
            a[p[i][j + y]] = p[i][j];
            if (p[i][j + y] - p[i][j] == n / 2) good += 1;
        }
        if (p[i].size() % 2 == 1) who = i;
    }
    vector<string> ans;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] - 'A' == who) {
            if (good == n / 2 && (ans.empty() || i == 0)) {
                string tmp = "";
                for (int j = 0; tmp.size() < n / 2; j++) {
                    if (i == j) continue;
                    tmp += s[j];
                }
                ans.push_back(tmp);
            }
            int p = a[prv[i]];
            int q = prv[i];
            if (abs(p - q) == n / 2 + (p > q)) good -= 1;
            a[p] = i;
            a[i] = p;
            if (abs(p - i) == n / 2 + (p < q)) good += 1;
            continue;
        }
        if (i > a[i] && abs(a[i] - i) == n / 2) good -= 1;
        if (i < a[i] && abs(a[i] - i) == n / 2 + 1) good -= 1;
        if (i > a[i] && abs(a[i] - i) == n / 2 + 1) good += 1;
        if (i < a[i] && abs(a[i] - i) == n / 2) good += 1;
    }
    if (ans.size() == 0) cout << "NOT POSSIBLE" << en;
    else if (ans.size() == 1 || (ans.size() == 2 && ans[0] == ans[1])) cout << ans[0] << en;
    else cout << "NOT UNIQUE" << en;
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:50:44: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |                 for (int j = 0; tmp.size() < n / 2; j++) {
      |                                 ~~~~~~~~~~~^~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65