Submission #243827

#	Time	Username	Problem	Language	Result	Execution time	Memory
243827		kimbj0709	Three Friends (BOI14_friends)	C++14	100 / 100	93 ms	26736 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000009
#define po 179
#define maxn 2000050
vector<int> powers(maxn,1);
int len;
string find(string input){
  string ret = "";
  int can1 = 0;
  int currsum = 0;
  int target = 0;
  for(int i=1;i<len/2+1;i++){
    currsum += (input.at(i)-'A')*powers[i-1];
    currsum %= mod;
  }
  for(int i=len/2+1;i<len;i++){
    target += (input.at(i)-'A')*powers[i-len/2-1];
    target %= mod;
  }
  if(currsum==target){
    can1++;
  }
  for(int i=0;i<len/2;i++){
    currsum -= (input.at(i+1)-'A')*powers[i];
    currsum += (input.at(i)-'A')*powers[i];
    currsum %= mod;
    currsum += mod*2;
    currsum %= mod;
    if(currsum==target){
      can1++;
    }
  }
  if(can1>0){
    for(int j=input.length()-1;j>input.length()-1-input.length()/2;j--){
      ret += input.at(j);
    }
    reverse(ret.begin(),ret.end());
  }
  return ret;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  string input;
  cin >> len >> input;
  if(len%2==0){
    cout << "NOT POSSIBLE";
    return 0;
  }
  for(int i=1;i<powers.size();i++){
    powers[i] = powers[i-1]*po;
    powers[i] %= mod;
  }
  string temp1 = find(input);
  reverse(input.begin(),input.end());
  string temp2 = find(input);
  reverse(temp2.begin(),temp2.end());
  if(temp1.length()==0&&temp2.length()==0){
    cout << "NOT POSSIBLE";
  }
  else if(temp1.length()==0&&temp2.length()!=0){
    cout << temp2;
  }
  else if(temp1.length()!=0&&temp2.length()==0){
    cout << temp1;
  }
  else if(temp1!=temp2){
    cout << "NOT UNIQUE";
  }
  else{
    cout << temp1;
  }


}

Compilation message (stderr)

friends.cpp: In function 'std::__cxx11::string find(std::__cxx11::string)':
friends.cpp:36:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=input.length()-1;j>input.length()-1-input.length()/2;j--){
                                ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
friends.cpp: In function 'int32_t main()':
friends.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<powers.size();i++){
               ~^~~~~~~~~~~~~~

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