Submission #880873

#	Time	Username	Problem	Language	Result	Execution time	Memory
880873		happiansf	Three Friends (BOI14_friends)	C++17	0 / 100	95 ms	52268 KiB

friends

#include <cstdio>
using namespace std;

#define N 2000001
#define A 29
#define P 10000007

int n;
int cnt, ans;
long long a[N + 1];
long long front_hash[N + 2];
long long back_hash[N + 2];

void input()
{
    char temp[N + 2];

    scanf("%d", &n);
    scanf("%s", &temp[1]);
    for(int i = 1; i <= n; i++)
    {
        a[i] = temp[i] - 'A';
    }

    //printf("%s", &temp[1]);
}

void check_front()
{
    long long pow_A = 1;
    long long ans_hash = 0;
    long long check_hash;

    for(int i = n / 2 + 2; i <= n; i++)
    {
        ans_hash = (ans_hash * A + a[i]) % P;
    }

    front_hash[0] = 0;
    for(int i = 1; i <= n / 2 + 1; i++)
    {
        front_hash[i] = (front_hash[i - 1] * A + a[i]) % P;
    }

    back_hash[n / 2 + 2] = 0;
    for(int i = n / 2 + 1; i >= 1; i--)
    {
        back_hash[i] = (back_hash[i + 1] + pow_A * a[i]) % P;
        pow_A = (pow_A * A) % P;
    }

    pow_A = 1;
    for(int i = n / 2 + 1; i >= 1; i--)
    {
        check_hash = (front_hash[i - 1] * pow_A + back_hash[i + 1]) % P;
        pow_A = (pow_A * A) % P;

        if(check_hash == ans_hash)
        {
            cnt++;
            ans = 1;
        }
    }
}

void check_back()
{
    long long pow_A = 1;
    long long ans_hash = 0;
    long long check_hash;

    for(int i = 1; i <= n / 2; i++)
    {
        ans_hash = (ans_hash * A + a[i]) % P;
    }

    front_hash[n / 2] = 0;
    for(int i = n / 2 + 1; i <= n; i++)
    {
        front_hash[i] = (front_hash[i - 1] * A + a[i]) % P;
    }

    back_hash[n + 1] = 0;
    for(int i = n; i >= n / 2 + 1; i--)
    {
        back_hash[i] = (back_hash[i + 1] + pow_A * a[i]) % P;
        pow_A = (pow_A * A) % P;
    }

    pow_A = 1;
    for(int i = n; i >= n / 2 + 1; i--)
    {
        check_hash = (front_hash[i - 1] * pow_A + back_hash[i + 1]) % P;
        pow_A = (pow_A * A) % P;

        if(check_hash == ans_hash)
        {
            cnt++;
            ans = 2;
        }
    }
}

void core()
{
    if(n % 2 == 0)
    {
        printf("NOT POSSIBLE");
        return;
    }

    check_front();
    check_back();

    if(cnt == 0)
    {
        printf("NOT POSSIBLE");
    }
    else if(cnt >= 2)
    {
        printf("NOT UNIQUE");
    }
    else
    {
        if(ans == 2)
        {
            for(int i = 1; i <= n / 2; i++)
            {
                printf("%c", a[i] + 'A');
            }
        }
        else
        {
            for(int i = n / 2 + 2; i <= n; i++)
            {
                printf("%c", a[i] + 'A');
            }
        }
    }
}

int main()
{
    input();
    core();
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'void core()':
friends.cpp:129:26: warning: format '%c' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  129 |                 printf("%c", a[i] + 'A');
      |                         ~^   ~~~~~~~~~~
      |                          |        |
      |                          int      long long int
      |                         %lld
friends.cpp:136:26: warning: format '%c' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  136 |                 printf("%c", a[i] + 'A');
      |                         ~^   ~~~~~~~~~~
      |                          |        |
      |                          int      long long int
      |                         %lld
friends.cpp: In function 'void input()':
friends.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
friends.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%s", &temp[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~

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