oj.uz

Submission #48349

# Submission time Handle Problem Language Result Execution time Memory
48349 2018-05-11T18:32:50 Z octopuses Palindromes (APIO14_palindrome) C++17
0 / 100
 258 ms 28020 KB 
#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define M (ll)(3e17)

using namespace std;
const int N = 300020;

char tmp[N];
int n;
int S[N][20], c[N], d[N], temp[N], cnt[N];
string a;

void sufsort()
{
  S[n + 1][0] = 0;
  int tot = 1;
  for(char ch = 'a'; ch <= 'z'; ++ ch)
    for(int i = 1; i <= n; ++ i)
      if(a[i] == ch)
        d[tot ++] = i;
  tot = 0;
  for(int i = 1; i <= n; ++ i)
  {
    if(a[d[i]] != a[d[i - 1]])
      tot ++;
    S[d[i]][0] = tot;
  }
  d[0] = n + 1;
  for(int i = 0; i <= n; ++ i)
    c[i] = d[i];
  for(int k = 1; k < 19; ++ k)
  {
    for(int i = 0; i <= n; ++ i)
      cnt[i] = 0;
    for(int i = 1; i <= n + 1; ++ i)
      cnt[S[i][k - 1]] ++;
    for(int i = 1; i <= n; ++ i)
      cnt[i] += cnt[i - 1];
    for(int i = n; i >= 0; -- i)
    {
      if(d[i] <= (1 << (k - 1)))
        continue;
      int j = d[i] - (1 << (k - 1));
      c[cnt[S[j][k - 1]] - 1] = j;
      cnt[S[j][k - 1]] --;
    }
    tot = 0;
    S[n + 1][k] = 0;
    for(int i = 1; i <= n; ++ i)
    {
      d[i] = c[i];
      if(S[c[i]][k - 1] != S[c[i - 1]][k - 1] || (c[i - 1] + (1 << (k - 1)) > n + 1) || S[c[i] + (1 << (k - 1))][k - 1] != S[c[i - 1] + (1 << (k - 1))][k - 1])
        tot ++;
      S[c[i]][k] = tot;
    }
  }
}


int main()
{
  scanf("%s", &tmp);
  n = strlen(tmp);
  a = '#' + string(tmp) + char('a' - 1);
  sufsort();
}
/*

*/

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:65:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[300020]' [-Wformat=]
   scanf("%s", &tmp);
               ~~~~^
palindrome.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &tmp);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 9628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 28020 KB Output isn't correct
2 Halted 0 ms 0 KB -