Submission #398969

#	Time	Username	Problem	Language	Result	Execution time	Memory
398969		faresbasbs	Three Friends (BOI14_friends)	C++14	100 / 100	242 ms	104032 KiB

friends

#include <bits/stdc++.h>
using namespace std;
int n,dp[2000002][2];
string s,c,d;
 
int ok(int curr , int tag){
	if(curr-tag == d.size()){
		return 1;
	}
	if(dp[curr][tag] != -1){
		return dp[curr][tag];
	}
	int ret = 0;
	if(!tag){
		ret = ok(curr+1,1);
	}
	if(c[curr] == d[curr-tag]){
		ret = max(ret,ok(curr+1,tag));
	}
	return dp[curr][tag] = ret;
}
 
int main(){
	cin >> n >> s;
	if(n%2 == 0){
		cout << "NOT POSSIBLE" << endl;
		return 0;
	}
	string t1 = "" , t2 = "" , ans1 = "" , ans2 = "";
	for(int i = 0 ; i < n/2 ; i += 1){
		t1 += s[i];
	}
	for(int i = n/2 ; i < n ; i += 1){
		t2 += s[i];
	}
	memset(dp,-1,sizeof dp);
	c = t2 , d = t1;
	if(ok(0,0)){
		ans1 = t1;
	}
	t1 = "" , t2 = "";
	for(int i = 0 ; i <= n/2 ; i += 1){
		t1 += s[i];
	}
	for(int i = n/2+1 ; i < n ; i += 1){
		t2 += s[i];
	}
	memset(dp,-1,sizeof dp);
	c = t1 , d = t2;
	if(ok(0,0)){
		ans2 = t2;
	}
	if(ans1 == "" && ans2 == ""){
		cout << "NOT POSSIBLE" << endl;
	}else if(ans1 == ""){
		cout << ans2 << endl;
	}else if(ans2 == ""){
		cout << ans1 << endl;
	}else if(ans1 == ans2){
		cout << ans1 << endl;
	}else{
		cout << "NOT UNIQUE" << endl;
	}
}

Compilation message (stderr)

friends.cpp: In function 'int ok(int, int)':
friends.cpp:7:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |  if(curr-tag == d.size()){
      |     ~~~~~~~~~^~~~~~~~~~~

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