oj.uz

Submission #42987

# Submission time Handle Problem Language Result Execution time Memory
42987 2018-03-07T13:58:59 Z PolyAtomicIon Three Friends (BOI14_friends) C++14
100 / 100
 407 ms 35956 KB 
#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <set>
#include <unordered_map>
#include <vector>
#define N 3111111
#define ll unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;

   ll n;
   ll p = 31,h[N],pw[N];
   ll mod = 1e9+7;
   string s;

   inline ll get_hash(int l,int r){
      if( l > r )
         return 0;
      if( l == 0 )
         return h[r] % mod;
      else
         return (h[r] - h[l-1] + mod) % mod;
   }

   unordered_map<ll,int> u;
   vector< pair<ll,int> > ans;

   set<char> t;

int main(){

   cin >> n;
   cin >> s;

   for(int i=0; i<n; i++){
      t.insert(s[i]);
   }

   if( n % 2 == 0 ){
      cout << "NOT POSSIBLE";
      return 0;
   }

   if( t.size() == 1 ){
      for(int i=0; i<n/2; i++){
         cout << s[i];
      }
      return 0;
   }

   pw[0] = 1;
   for(int i=1; i<=n; i++){
      pw[i] = pw[i-1];
      pw[i] = (pw[i]*p) % mod;
   }

   h[0] = s[0]-'A'+1;
   for(int i=1; i<n; i++){
      h[i] = h[i-1];
      h[i] = ( h[i] % mod + ((s[i] - 'A'+1)*pw[i]) % mod);
      h[i] %= mod;
   }

   int md = n/2;

   for(int i=0; i<=md; i++){

      ll a1 = get_hash(0,i-1);
      ll a2 = get_hash(md+1,md+1+i-1);
      a1 = (a1 * pw[md+1]) % mod;

      //cout << s.substr(0,i) << " " << s.substr(md+1,i) << " : ";

      ll b1 = get_hash(i+1,i+1+md-i-1);
      ll b2 = get_hash(md+1+i,md+1+i+md-i-1);
      b1 = (b1 * pw[md]) % mod;

      //cout << s.substr(i+1,md-i) << ' ' << s.substr( md+1+i,md-i ) << '\n';

      //cout << i << " : " << a1 << ' ' << a2 << ' ' << b1 << ' ' << b2 << '\n';

      if( a1 == a2 && b1 == b2 && u[(a1+b1)%mod] == 0 ){
         ans.pb( mp((a1+b1)%mod,md+1) );
         u[(a1+b1)%mod]=1;
      }

   }

   int cur = 0;
   for(int i=md; i<n; i++){

      ll a1 = get_hash(0,cur-1);
      ll a2 = get_hash(i-cur,i-1);
      a1 = (a1 * pw[md]) % mod;

      //cout << s.substr(0,cur) << " " << s.substr(i-cur,cur) << " : ";

      ll b1 = get_hash(cur,md-1);
      ll b2 = get_hash(i+1,n-1);
      b1 = (b1 * pw[md+1]) % mod;

      //cout << s.substr(cur,md-cur) << ' ' << s.substr( i+1,md-cur ) << '\n';

      //cout << i << " : " << a1 << ' ' << a2 << ' ' << b1 << ' ' << b2 << '\n';

      if( a1 == a2 && b1 == b2 && u[(a1+b1)%mod] == 0 ){
         ans.pb( mp((a1+b1)%mod,0) );
         u[(a1+b1)%mod]=1;
      }
      cur++;
   }
   /*
   9
   FROGGFROG
   NOT UNIQUE
   *//*
   cout << ans.size() << endl;
   for(int i=0; i<ans.size(); i++){
      cout << ans[i].first << ' ' << ans[i].second << endl;
   }*/
   if( ans.size() == 0 ){
      cout << "NOT POSSIBLE";
   }
   else if( ans.size() > 1 ){
      cout << "NOT UNIQUE";
   }
   else{
      int id = ans[0].second;
      cout << s.substr(id,md);
   }

   return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<n; i++){
                  ^
friends.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<n/2; i++){
                     ^
friends.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<=n; i++){
                  ^
friends.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<n; i++){
                  ^
friends.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=md; i<n; i++){
                   ^

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 572 KB Output is correct
7 Correct 1 ms 576 KB Output is correct
8 Correct 1 ms 576 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 620 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct
20 Correct 1 ms 620 KB Output is correct
21 Correct 2 ms 620 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 1 ms 744 KB Output is correct
24 Correct 1 ms 744 KB Output is correct
25 Correct 2 ms 744 KB Output is correct
26 Correct 2 ms 744 KB Output is correct
27 Correct 1 ms 744 KB Output is correct
28 Correct 1 ms 744 KB Output is correct
29 Correct 1 ms 744 KB Output is correct
30 Correct 2 ms 744 KB Output is correct
31 Correct 1 ms 744 KB Output is correct
32 Correct 1 ms 744 KB Output is correct
33 Correct 1 ms 744 KB Output is correct
34 Correct 1 ms 744 KB Output is correct
35 Correct 1 ms 744 KB Output is correct
36 Correct 1 ms 744 KB Output is correct
37 Correct 2 ms 744 KB Output is correct
38 Correct 1 ms 744 KB Output is correct
39 Correct 1 ms 744 KB Output is correct
40 Correct 1 ms 744 KB Output is correct
41 Correct 1 ms 744 KB Output is correct
42 Correct 2 ms 744 KB Output is correct
43 Correct 1 ms 744 KB Output is correct
44 Correct 2 ms 752 KB Output is correct
45 Correct 2 ms 752 KB Output is correct
46 Correct 2 ms 752 KB Output is correct
47 Correct 2 ms 752 KB Output is correct
48 Correct 2 ms 752 KB Output is correct
49 Correct 1 ms 752 KB Output is correct
50 Correct 1 ms 752 KB Output is correct
51 Correct 2 ms 752 KB Output is correct
52 Correct 2 ms 752 KB Output is correct
53 Correct 2 ms 752 KB Output is correct
54 Correct 2 ms 752 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 35876 KB Output is correct
2 Correct 404 ms 35948 KB Output is correct
3 Correct 404 ms 35948 KB Output is correct
4 Correct 403 ms 35948 KB Output is correct
5 Correct 394 ms 35956 KB Output is correct
6 Correct 81 ms 35956 KB Output is correct
7 Correct 105 ms 35956 KB Output is correct
8 Correct 296 ms 35956 KB Output is correct
9 Correct 294 ms 35956 KB Output is correct
10 Correct 300 ms 35956 KB Output is correct
11 Correct 270 ms 35956 KB Output is correct
12 Correct 2 ms 35956 KB Output is correct
13 Correct 1 ms 35956 KB Output is correct
14 Correct 1 ms 35956 KB Output is correct
15 Correct 1 ms 35956 KB Output is correct
16 Correct 1 ms 35956 KB Output is correct
17 Correct 1 ms 35956 KB Output is correct
18 Correct 1 ms 35956 KB Output is correct
19 Correct 1 ms 35956 KB Output is correct
20 Correct 1 ms 35956 KB Output is correct
21 Correct 1 ms 35956 KB Output is correct
22 Correct 1 ms 35956 KB Output is correct
23 Correct 1 ms 35956 KB Output is correct
24 Correct 1 ms 35956 KB Output is correct
25 Correct 1 ms 35956 KB Output is correct
26 Correct 1 ms 35956 KB Output is correct
27 Correct 1 ms 35956 KB Output is correct
28 Correct 1 ms 35956 KB Output is correct
29 Correct 1 ms 35956 KB Output is correct
30 Correct 1 ms 35956 KB Output is correct
31 Correct 1 ms 35956 KB Output is correct
32 Correct 1 ms 35956 KB Output is correct
33 Correct 1 ms 35956 KB Output is correct
34 Correct 1 ms 35956 KB Output is correct
35 Correct 1 ms 35956 KB Output is correct
36 Correct 2 ms 35956 KB Output is correct
37 Correct 1 ms 35956 KB Output is correct
38 Correct 1 ms 35956 KB Output is correct
39 Correct 1 ms 35956 KB Output is correct
40 Correct 1 ms 35956 KB Output is correct
41 Correct 1 ms 35956 KB Output is correct
42 Correct 1 ms 35956 KB Output is correct
43 Correct 1 ms 35956 KB Output is correct
44 Correct 1 ms 35956 KB Output is correct
45 Correct 1 ms 35956 KB Output is correct
46 Correct 2 ms 35956 KB Output is correct
47 Correct 1 ms 35956 KB Output is correct
48 Correct 1 ms 35956 KB Output is correct
49 Correct 1 ms 35956 KB Output is correct
50 Correct 1 ms 35956 KB Output is correct
51 Correct 1 ms 35956 KB Output is correct
52 Correct 1 ms 35956 KB Output is correct
53 Correct 1 ms 35956 KB Output is correct
54 Correct 1 ms 35956 KB Output is correct