oj.uz

Submission #397677

# Submission time Handle Problem Language Result Execution time Memory
397677 2021-05-02T19:57:15 Z ly20 Three Friends (BOI14_friends) C++17
100 / 100
 217 ms 24868 KB 
#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

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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 276 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 300 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 1 ms 204 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 1 ms 204 KB Output is correct
45 Correct 1 ms 204 KB Output is correct
46 Correct 1 ms 204 KB Output is correct
47 Correct 1 ms 204 KB Output is correct
48 Correct 1 ms 332 KB Output is correct
49 Correct 1 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 208 KB Output is correct
54 Correct 1 ms 204 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 18200 KB Output is correct
2 Correct 199 ms 18096 KB Output is correct
3 Correct 204 ms 18200 KB Output is correct
4 Correct 205 ms 18176 KB Output is correct
5 Correct 202 ms 18164 KB Output is correct
6 Correct 131 ms 8124 KB Output is correct
7 Correct 217 ms 24868 KB Output is correct
8 Correct 132 ms 18776 KB Output is correct
9 Correct 180 ms 18704 KB Output is correct
10 Correct 184 ms 18732 KB Output is correct
11 Correct 119 ms 17864 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 1 ms 204 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 1 ms 204 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 1 ms 204 KB Output is correct
45 Correct 1 ms 204 KB Output is correct
46 Correct 1 ms 204 KB Output is correct
47 Correct 1 ms 208 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 1 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 204 KB Output is correct
54 Correct 1 ms 204 KB Output is correct