Submission #48349

#	Time	Username	Problem	Language	Result	Execution time	Memory
48349		octopuses	Palindromes (APIO14_palindrome)	C++17	0 / 100	258 ms	28020 KiB

palindrome

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27