Submission #397677

#	Time	Username	Problem	Language	Result	Execution time	Memory
397677		ly20	Three Friends (BOI14_friends)	C++17	100 / 100	217 ms	24868 KiB

friends

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2123456;
int v[MAXN];
vector <int> resp;
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        char a;
        scanf(" %c", &a);
        v[i] = a - 'A';
    }
    if(n % 2 == 0) {
        printf("NOT POSSIBLE\n");
        return 0;
    }
    int tresp = n / 2;
    vector <int> pref, sulf;
    for(int i = 0; i < n; i++) {
        if(i <= tresp) pref.push_back(v[i]);
        else sulf.push_back(v[i]);
    }
    int eqs = 0, eqp = 0;
    for(int i = sulf.size() - 1; i >= 0; i--) {
        if(sulf[i] == pref[i + 1]) eqs++;
        else break;
    }
    for(int i = 0; i < sulf.size(); i++) {
        if(sulf[i] == pref[i]) eqp++;
        else break;
    }
    //printf("%d %d\n", eqp, eqs);
    for(int i = 0; i <= tresp; i++) {
        if(eqp >= i && (tresp - i) <= eqs) resp.push_back(i);
    }
    pref.clear(); sulf.clear();
    for(int i = 0; i < n; i++) {
        if(i < tresp) sulf.push_back(v[i]);
        else pref.push_back(v[i]);
    }
    /*for(int i = 0; i < sulf.size(); i++) printf("%d ", sulf[i]);
    printf("\n");
    for(int i = 0; i < pref.size(); i++) printf("%d ", pref[i]);
    printf("\n");
    */
    eqs = 0, eqp = 0;
    for(int i = sulf.size() - 1; i >= 0; i--) {
        if(sulf[i] == pref[i + 1]) eqs++;
        else break;
    }
    for(int i = 0; i < sulf.size(); i++) {
        if(sulf[i] == pref[i]) eqp++;
        else break;
    }
    //printf("%d %d\n", eqs, eqp);
    for(int i = 0; i <= tresp; i++) {
        if(eqp >= i && (tresp - i) <= eqs) {
            //printf("oi\n");
            if(i != 0) resp.push_back(i + tresp);
        }
    }
    /*while(!resp.empty()) {
        printf("%d\n", (*resp.begin()));
        resp.erase(resp.begin());
    }*/
    bool ok = true;
    for(int i = 1; i < resp.size(); i++) {
        if(resp[i] - 1 != resp[i - 1] || v[resp[i]] != v[resp[i - 1]]) ok = false;
    }
    if(resp.size() == 0) {
        printf("NOT POSSIBLE\n");
    }
    else if(!ok) {
        printf("NOT UNIQUE\n");
    }
    else {
        int at = 0, cur = 0;
        int rs = resp[0];
        while(at < tresp) {
            if(rs != cur) {
                at++;
                printf("%c", v[cur] + 'A');
            }
            cur++;
        }
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < sulf.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
friends.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < sulf.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
friends.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 1; i < resp.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
friends.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
friends.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |         scanf(" %c", &a);
      |         ~~~~~^~~~~~~~~~~

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