oj.uz

Submission #852277

# Submission time Handle Problem Language Result Execution time Memory
852277 2023-09-21T14:13:42 Z NK_ Three Friends (BOI14_friends) C++17
0 / 100
 28 ms 22780 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	string S; cin >> S;

	vi F(26); for(auto& c : S) F[c-'a']++;

	if (N % 2 == 0) {
		cout << "NOT POSSIBLE" << nl;
		exit(0-0);
	}

	int M = (N - 1) / 2;

	vi OUT(N), IN(N);
	// IN[i] = A[i] == A[i + M + 1];
	// OUT[i] = A[i] == A[i + M] 


	for(int i = 0; i < N; i++) {
		if (i+M+1 < N) IN[i] = (S[i] == S[i+M+1]);
		if (i+M < N) OUT[i] = (S[i] == S[i+M]);
	}

	string ans1, ans2;

	// START WITH IN THEN SWITCH TO OUT
	{
		bool aft = 0;
		for(int i = 0; i < N; i++) {
			if (sz(ans1) == M) break;
			if (aft) {
				if (OUT[i]) ans1 += S[i];
				else break;
			} else {
				if (IN[i]) ans1 += S[i];
				else aft = 1;
			}		
		}
	}

	// START WITH OUT THEN SWITCH TO IN

	{ 
		bool aft = 0;
		for(int i = 0; i < N; i++) {
			if (sz(ans2) == M) break;
			if (aft) {
				if (IN[i]) ans2 += S[i];
				else break;
			} else {
				if (OUT[i]) ans2 += S[i];
				else aft = 1;
			}		
		}
	}	

	if (ans1 == ans2) ans2 = "";

	if (sz(ans1) == M && sz(ans2) == M) cout << "NOT UNIQUE" << nl;
	else if (sz(ans1) == M) cout << ans1 << nl; 
	else if (sz(ans2) == M) cout << ans2 << nl;
	else cout << "NOT POSSIBLE" << nl;

	exit(0-0);
}

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22012 KB Output is correct
2 Correct 16 ms 21760 KB Output is correct
3 Correct 14 ms 21924 KB Output is correct
4 Correct 17 ms 21756 KB Output is correct
5 Correct 18 ms 21748 KB Output is correct
6 Correct 8 ms 2548 KB Output is correct
7 Correct 28 ms 22780 KB Output is correct
8 Correct 17 ms 20788 KB Output is correct
9 Correct 17 ms 21556 KB Output is correct
10 Correct 14 ms 20732 KB Output is correct
11 Correct 12 ms 16628 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -