제출 #648258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648258		ymm	세 명의 친구들 (BOI14_friends)	C++17	100 / 100	99 ms	13092 KiB

friends

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 2'000'010;
char s[N];
int n;

int fenN[N], fenN1[N];

template<int fen[]>
void add(int i)
{
	++i;
	while (i < N) {
		fen[i]++;
		i += i & -i;
	}
}
template<int fen[]>
int get(int r)
{
	int ans = 0;
	while (r > 0) {
		ans += fen[r];
		r -= r & -r;
	}
	return ans;
}
template<int fen[]>
int get(int l, int r)
{
	return get<fen>(r) - get<fen>(l);
}

bool test(int i)
{
	if (i <= n)
		return get<fenN1>(0, i) + get<fenN>(i+1, n+1) == n;
	else
		return get<fenN>(0, i-n) + get<fenN1>(i-n, n) == n;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> s;
	if (n%2 == 0) {
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	n = (n-1)/2;
	Loop (i,0,n+1)
		if (s[i] == s[i+n])
			add<fenN>(i);
	Loop (i,0,n)
		if (s[i] == s[i+n+1])
			add<fenN1>(i);
	vector<int> pos;
	Loop (i,0,2*n+1) {
		if (i && s[i-1] == s[i])
			continue;
		if (test(i))
			pos.push_back(i);
	}
	if (pos.empty())
		cout << "NOT POSSIBLE\n";
	else if (pos.size() > 1)
		cout << "NOT UNIQUE\n";
	else if (pos[0] <= n)
		cout << s + n+1 << '\n';
	else {
		s[n] = 0;
		cout << s << '\n';
	}
}

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65