답안 #91886 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91886	2018-12-31T07:16:00 Z	karma	세 명의 친구들 (BOI14_friends)	C++11	100 / 100	129 ms	36692 KB

friends

#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a, _b = b; i <= _b; ++i)
#define Ford(i, a, b) for(int i = a, _b = b; i >= _b; --i)
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long
#define Print(x)      cerr << #x << "is " << x << '\n';
#define pb            push_back
#define X             first
#define Y             second
//#define Karma

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 2e6 + 7;
const ll Base = 35;
const ll mod = 2147483647;

ll Hash[N], p[N], n, cnt, pos;
string s;
unordered_map<ll, bool> mmap;

ll GetHash(int l, int r)
{
    return (Hash[r] - Hash[l - 1] * p[r - l + 1] + mod * mod) % mod;
}

void Enter()
{
     cin >> n >> s;
     p[0] = 1;
     s = ' ' + s;
     For(i, 1, n + 3) p[i] = (p[i - 1] * Base) % mod;
     For(i, 1, n) Hash[i] = (Hash[i - 1] * Base + s[i] - 'A' + 1) % mod;
     if(n % 2 == 0) {cout << "NOT POSSIBLE"; exit(0);}
}

void Solve()
{
     if(GetHash(2, (n + 1) / 2) == GetHash((n + 3) / 2, n)) ++cnt, pos = 1, mmap[GetHash(2, n / 2 + 1)] = 1;
     if(GetHash(1, n / 2) == GetHash(n / 2 + 1, n - 1) && !mmap[GetHash(1, n / 2)]) ++cnt, pos = n, mmap[GetHash(1, n / 2)] = 1;
     if(GetHash(1, n / 2) == GetHash(n / 2 + 2, n) && !mmap[GetHash(1, n / 2)]) ++cnt, pos = n / 2 + 1, mmap[GetHash(1, n / 2)] = 1;
     For(i, 2, n - 1)
     {
         if(i < n / 2 + 1)
         {
            ll compare = GetHash(n / 2 + 2, n), st = GetHash(1, i - 1), len = n / 2 + 1 - i;
            if(mmap[compare]) continue;
            ll en = GetHash(i + 1, i + len);
            ll connect = ((st * p[len]) % mod + en) % mod;
            if(connect == compare) ++cnt, pos = i, mmap[compare] = 1;
         }
         else if(i > n / 2 + 1)
         {
            ll compare = GetHash(1, n / 2), st = GetHash(n / 2 + 1, i - 1), len = n - i;
            if(mmap[compare]) continue;
            ll en = GetHash(n - len + 1, n);
            ll connect = (st * p[len] % mod) + en;
            connect %= mod;
            if(connect == compare) ++cnt, pos = i, mmap[compare] = 1;
         }
     }
     if(cnt > 1) cout << "NOT UNIQUE";
     else if(cnt == 0) cout << "NOT POSSIBLE";
     else
     {
         if(pos >= n / 2 + 1) For(i, 1, n / 2) cout << s[i];
         else For(i, n / 2 + 2, n) cout << s[i];
     }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef Karma
    freopen(FileName".inp", "r", stdin);
    freopen(FileName".out", "w", stdout);
#endif // Karma

    Enter();
    Solve();

    return 0;
}

Subtask #1
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	380 KB	Output is correct
6	Correct	1 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	1 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	380 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	1 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	1 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	1 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	2 ms	380 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	1 ms	376 KB	Output is correct
33	Correct	2 ms	376 KB	Output is correct
34	Correct	2 ms	376 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	2 ms	376 KB	Output is correct
37	Correct	1 ms	376 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	2 ms	376 KB	Output is correct
40	Correct	2 ms	376 KB	Output is correct
41	Correct	2 ms	376 KB	Output is correct
42	Correct	1 ms	376 KB	Output is correct
43	Correct	2 ms	376 KB	Output is correct
44	Correct	2 ms	376 KB	Output is correct
45	Correct	2 ms	376 KB	Output is correct
46	Correct	2 ms	376 KB	Output is correct
47	Correct	2 ms	376 KB	Output is correct
48	Correct	2 ms	376 KB	Output is correct
49	Correct	2 ms	376 KB	Output is correct
50	Correct	2 ms	380 KB	Output is correct
51	Correct	2 ms	376 KB	Output is correct
52	Correct	2 ms	376 KB	Output is correct
53	Correct	2 ms	376 KB	Output is correct
54	Correct	2 ms	376 KB	Output is correct

Subtask #2
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	34672 KB	Output is correct
2	Correct	120 ms	34672 KB	Output is correct
3	Correct	124 ms	34800 KB	Output is correct
4	Correct	126 ms	34800 KB	Output is correct
5	Correct	129 ms	34672 KB	Output is correct
6	Correct	61 ms	35684 KB	Output is correct
7	Correct	114 ms	36692 KB	Output is correct
8	Correct	96 ms	32184 KB	Output is correct
9	Correct	116 ms	32992 KB	Output is correct
10	Correct	111 ms	33076 KB	Output is correct
11	Correct	92 ms	30008 KB	Output is correct
12	Correct	1 ms	376 KB	Output is correct
13	Correct	2 ms	380 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	1 ms	380 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	1 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	1 ms	376 KB	Output is correct
22	Correct	1 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	380 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	1 ms	376 KB	Output is correct
33	Correct	2 ms	376 KB	Output is correct
34	Correct	2 ms	376 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	2 ms	376 KB	Output is correct
37	Correct	2 ms	376 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	2 ms	376 KB	Output is correct
40	Correct	2 ms	376 KB	Output is correct
41	Correct	1 ms	376 KB	Output is correct
42	Correct	2 ms	376 KB	Output is correct
43	Correct	2 ms	376 KB	Output is correct
44	Correct	2 ms	376 KB	Output is correct
45	Correct	2 ms	376 KB	Output is correct
46	Correct	2 ms	376 KB	Output is correct
47	Correct	2 ms	380 KB	Output is correct
48	Correct	2 ms	376 KB	Output is correct
49	Correct	2 ms	376 KB	Output is correct
50	Correct	2 ms	376 KB	Output is correct
51	Correct	2 ms	376 KB	Output is correct
52	Correct	2 ms	376 KB	Output is correct
53	Correct	2 ms	376 KB	Output is correct
54	Correct	2 ms	376 KB	Output is correct

답안 #91886

Compilation message

Subtask #1 35.0 / 35.0

Subtask #2 65.0 / 65.0

Subtask #1
35.0 / 35.0

Subtask #2
65.0 / 65.0