Submission #735662

#	Time	Username	Problem	Language	Result	Execution time	Memory
735662		josanneo22	Three Friends (BOI14_friends)	C++17	35 / 100	1079 ms	73232 KiB

friends

#include<bits/stdc++.h> 
#include<unordered_map>
using namespace std;

#define int long long
#define mp make_pair
#define fi first
#define se second
set<int> st;
unordered_map<string,int> ans;
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	string s; cin >> s;
	if (n % 2 == 0) {
		cout << "NOT POSSIBLE\n";
		return 0;
	}
	int pt = 0, jump = n / 2;
	string p = "";
	for (int i = 1; i < n; i++) {
		p += s[i];
	}
	for (int i = 0; i < p.size(); i++) {
		if (i + jump <= p.size() - 1 && p[i] != p[i + jump]) {
			st.insert(i);
			st.insert(i + jump);
		}
	}
	while (pt <= n - 1) {
		if (st.size() == 0) {
			ans[p]=1;
		}
		p[pt] = s[pt];
		auto pos = st.find(pt);
		if (pos != st.end()) st.erase(pos); 
		if (pt + jump <= n - 2) {
			pos = st.find(pt + jump);
			if (pos != st.end()) st.erase(pos);
		}
		if (pt - jump <= n - 2){ 
			pos = st.find(pt - jump);
			if (pos != st.end()) st.erase(pos); 
		}
		if (pt + jump <= n - 2 && p[pt] != p[pt + jump]) {
			st.insert(pt);
			st.insert(pt + jump);
		}
		if(pt -jump>=0 && p[pt] != p[pt - jump]){
			st.insert(pt);
			st.insert(pt - jump);
		}  
		pt++;
	}
	if (ans.size()==1){
		for(auto it=ans.begin();it!=ans.end();it++){
			string save=it->first;
			cout<<save.substr(0,n/2);
			return 0;
		}
	}
	else if(ans.size()==0) cout << "NOT POSSIBLE\n";
	else cout << "NOT UNIQUE";
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:24:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
friends.cpp:25:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   if (i + jump <= p.size() - 1 && p[i] != p[i + jump]) {
      |       ~~~~~~~~~^~~~~~~~~~~~~~~

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