oj.uz

답안 #26169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26169 2017-06-28T07:59:05 Z chpipis 수열 (BOI14_sequence) C++11
0 / 100
 19 ms 19596 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 2e6 + 5;
const int BASE = 29;
const int MOD = 1e9 + 7;

inline int mul_mod(int a, int b) {
    return a * 1LL * b % MOD;
}

inline void add_mod(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

inline void sub_mod(int &a, int b) {
    a -= b;
    if (a < 0) a += MOD;
}

char str[MAXN];
int h[MAXN], bpow[MAXN];

int get_hash(int i, int j) {
    int ret = h[j];
    sub_mod(ret, mul_mod(h[i - 1], bpow[j - i + 1]));
    return ret;
}

int main() {
    bpow[0] = 1;
    for (int i = 1; i < MAXN; i++)
        bpow[i] = mul_mod(bpow[i - 1], BASE);
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    scanf("%s", str + 1);
    if (!(n & 1)) {
        puts("NOT POSSIBLE");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        h[i] = mul_mod(h[i - 1], BASE);
        add_mod(h[i], str[i] - 'A' + 1);
    }
    int ans = -1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        int left, right;
        if (i <= (n / 2) + 1) {
            left = get_hash(1, i - 1);
            left = mul_mod(left, bpow[(n / 2) - (i - 1)]);
            add_mod(left, get_hash(i + 1, i + 1 + (n / 2) - (i - 1) - 1));

            right = get_hash(n - (n / 2) + 1, n);
        } else {
            left = get_hash(1, n / 2);

            int len = n - (i + 1) + 1;

            right = get_hash((n / 2) + 1, (n / 2) + 1 + (n / 2) - len - 1);
            right = mul_mod(right, bpow[len]);
            add_mod(right, get_hash(i + 1, n));
        }
        if (left == right) {
            cnt++;
            ans = i;
            //printf("I can replace char at pos %d\n", i);
        }
    }
    if (cnt > 1)
        puts("NOT UNIQUE");
    else if (cnt == 0)
        puts("NOT POSSIBLE");
    else {
        for (int i = 1, c = 0; c < (n / 2); i++) {
            if (ans == i) continue;
            c++;
            pc(str[i]);
        }
        pc('\n');
    }
    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:86:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
sequence.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str + 1);
                         ^

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 19596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 19596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 19596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 19596 KB Output isn't correct
2 Halted 0 ms 0 KB -