oj.uz

Submission #24320

# Submission time Handle Problem Language Result Execution time Memory
24320 2017-06-04T21:56:47 Z Bruteforceman Three Friends (BOI14_friends) C++11
0 / 100
 73 ms 37464 KB 
#include "bits/stdc++.h"
using namespace std;
int n;
string s;

const int mod = 1000000000 + 7;
const int base = 31;
long long p[2000010];
long long power[2000010];

long long hasher(int x, int y) {
	if(x > y) return 0;
	long long ans = (p[y] - power[y-x+1] * p[x-1]) % mod;
	if(ans < 0) ans += mod;
	return ans;
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie(0);

	cin >> n;
	cin >> s;
	n = s.size();
	s = "&" + s;

	power[0] = 1;
	p[0] = 0;
	for(int i = 1; i <= n; i++) {
		p[i] = p[i-1] * base + (s[i] - 'A');
		p[i] %= mod; 
		power[i] = power[i-1] * base;
		power[i] %= mod;
	}

	vector <int> can;
	for(int i = 1; i <= (n>>1); i++) {
		long long p1 = hasher(1, i-1);
		long long p2 = hasher(i+1, (n>>1) + 1);
		long long whole = p1 * power[(n >> 1) - i + 1] + p2;
		whole %= mod;
		if(whole == hasher((n >> 1) + 2, n)) {
			can.push_back(i);
		}
	}
	for(int i = (n>>1) + 1; i <= n; i++) {
		long long p1 = hasher((n>>1) + 1, i-1);
		long long p2 = hasher(i+1, n);
		long long whole = p1 * power[n - i] + p2;
		whole %= mod;
		if(whole == hasher(1, n >> 1)) {
			can.push_back(i);
		}
	}
	if(can.empty()) {
		cout << "NOT POSSIBLE" << endl;
	} else if (can.size() == 1) {
		s.erase(s.begin() + can.front());
		for(int i = 1; i <= (n>>1); i++) {
			cout << s[i];
		}
		cout << endl;
	} else {
		cout << "NOT UNIQUE" << endl;
	}
	return 0;
}

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33428 KB Output is correct
2 Correct 0 ms 33428 KB Output is correct
3 Correct 0 ms 33428 KB Output is correct
4 Correct 0 ms 33428 KB Output is correct
5 Correct 0 ms 33428 KB Output is correct
6 Correct 0 ms 33428 KB Output is correct
7 Correct 0 ms 33428 KB Output is correct
8 Correct 0 ms 33428 KB Output is correct
9 Correct 0 ms 33428 KB Output is correct
10 Correct 0 ms 33428 KB Output is correct
11 Correct 0 ms 33428 KB Output is correct
12 Correct 0 ms 33428 KB Output is correct
13 Correct 0 ms 33428 KB Output is correct
14 Correct 0 ms 33428 KB Output is correct
15 Correct 0 ms 33428 KB Output is correct
16 Correct 0 ms 33428 KB Output is correct
17 Correct 0 ms 33428 KB Output is correct
18 Correct 0 ms 33428 KB Output is correct
19 Correct 0 ms 33428 KB Output is correct
20 Correct 0 ms 33428 KB Output is correct
21 Correct 0 ms 33428 KB Output is correct
22 Correct 0 ms 33428 KB Output is correct
23 Correct 0 ms 33428 KB Output is correct
24 Incorrect 0 ms 33428 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 37464 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -