oj.uz

답안 #880873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880873 2023-11-30T07:43:51 Z happiansf 세 명의 친구들 (BOI14_friends) C++17
0 / 100
 95 ms 52268 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6312 KB Output is correct
4 Incorrect 2 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 52052 KB Output is correct
2 Correct 83 ms 52048 KB Output is correct
3 Correct 83 ms 52268 KB Output is correct
4 Correct 83 ms 52124 KB Output is correct
5 Incorrect 54 ms 51024 KB Output isn't correct
6 Halted 0 ms 0 KB -