제출 #57423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57423		PeppaPig	세 명의 친구들 (BOI14_friends)	C++14	0 / 100	87 ms	66440 KiB

friends

#include <bits/stdc++.h>

#define pll pair<long long, long long>
#define x first
#define y second

using namespace std;

const int N = 2e6 + 5;

pll add(pll a, pll b) { return pll(a.x + b.x, a.y + b.y); }
pll sub(pll a, pll b) { return pll(a.x - b.x, a.y - b.y); }
pll mul(pll a, pll b) { return pll(a.x * b.x, a.y * b.y); }

pll prm = pll(69LL, 420LL);
pll pwr[N];

int n, mid;
pll dp[N];
char A[N];
vector<pll> ans;

int main() {
	pwr[0] = pll(1LL, 1LL);
	for(int i = 1; i < N; i++) pwr[i] = mul(pwr[i - 1], prm);

	scanf("%d", &n);
	if(!(n & 1)) return !printf("NOT POSSIBLE");
	mid = n >> 1;
	scanf("%s", A + 1);

	for(int i = 1; i <= n; i++) dp[i] = add(mul(dp[i - 1], prm), pll(A[i], A[i]));
	for(int i = 1; i <= n; i++) {
		pll lhs, rhs;
		if(i <= mid) {
			lhs = add(mul(dp[i - 1], pwr[mid - i + 1]), sub(dp[mid + 1], mul(dp[i], pwr[mid - i + 1])));
			rhs = sub(dp[n], mul(dp[mid + 1], pwr[mid]));
			if(lhs == rhs) ans.emplace_back(mid + 2, n);
		} else {
			lhs = dp[mid];
			rhs = add(mul(sub(dp[i - 1], mul(dp[mid], pwr[i - mid - 1])), pwr[n - i]), sub(dp[n], mul(dp[i], pwr[n - i])));
			if(lhs == rhs) ans.emplace_back(1, mid);
		}
	}

	bool hell = true;
	for(int i = 1; i <= mid; ++i) hell &= A[i] == A[mid+i+1];
	if(ans.size() == 0 or n % 2 == 0) puts("NOT POSSIBLE");
	else if(ans.size() == 1 || hell)  A[ans.begin()->y+1] = 0, puts(A+ans.begin()->x);
	else if(ans.size() > 1) puts("NOT UNIQUE");

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

friends.cpp: In function 'int main()':
friends.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
friends.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A + 1);
  ~~~~~^~~~~~~~~~~~~

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