oj.uz

Submission #26735

# Submission time Handle Problem Language Result Execution time Memory
26735 2017-07-05T10:54:02 Z model_code Periodicity (POI11_okr) C++14
100 / 100
 59 ms 6848 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Okresowosc                                       *
 *   Autor:             Jakub Radoszewski                                *
 *   Zlozonosc czasowa: O(n)                                             *
 *   Opis:              Rozwiazanie alternatywne                         *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define REP(I,N) for(int I=0;I<(N);I++)
#define ALL(X) (X).begin(),(X).end()
#define PB push_back
#define SIZE(x) ((int)(x).size())

typedef vector<int> VI;


#define MAX 200010

/* KMP */
VI prefsufy(const string &s,int n)
{
  int p[MAX];
  p[0]=p[1]=0;
  FOR(i,2,n)
  {
    int j=p[i-1];
    while (j>0 && s[j+1]!=s[i]) j=p[j];
    if (s[j+1]==s[i]) j++;
    p[i]=j;
  }
  VI t;
  int j=p[n];
  while (j>0) { t.PB(j); j=p[j]; }
  reverse(ALL(t));
  return t;
}

VI dopelnienie(VI ps,int n)
{
  VI ok;
  REP(i,SIZE(ps)) ok.PB(n-ps[i]);
  return ok;
}


string doit(VI &ps,int n)
{
  string s;
  if (ps.empty())
  {
    if (n==1) s="0";
    else
    {
      REP(i,n-1) s+='0';
      s+='1';
    }
    return s;
  }

  VI ok=dopelnienie(ps,n);
  if (ok.back()<=n/2)
  {
    int o=ok.back();
    int ile=((n/o)-1)*o;
    while (!ok.empty() && ok.back()<=ile) { ok.pop_back(); ps.pop_back(); }
    REP(i,SIZE(ok)) ok[i]-=ile;
    int n1=n-ile;
    ps=dopelnienie(ok,n1);
    s=doit(ps,n1);
    while (SIZE(s)<n) s+=string(s.end()-o,s.end());
    return s;
  }
  
  int p=ps.back();
  ps.pop_back();
  string s1=doit(ps,p);
  s=s1;
  REP(i,n-2*p) s+='0';
  s+=s1;

  VI ps1=prefsufy(string("a")+s,n);
  if (!ps1.empty())
  {
    int o1=n-ps1.back();
    if (o1<=n/2) s[SIZE(s1)+n-2*p-1]='1';
  }
  return s;
}

int main()
{
  int ile;
  scanf("%d",&ile);
  while (ile--)
  {
    char st[MAX];
    scanf("%s",st);
    int n=strlen(st);
    VI ps=prefsufy(string("a")+string(st),n);
    string s=doit(ps,n);
    puts(s.c_str());
  }
  return 0;
}

Compilation message

okr.cpp: In function 'int main()':
okr.cpp:104:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&ile);
                   ^
okr.cpp:108:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",st);
                   ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2788 KB Output is correct
2 Correct 0 ms 2784 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2784 KB Output is correct
2 Correct 0 ms 2788 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2788 KB Output is correct
2 Correct 0 ms 2788 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2788 KB Output is correct
2 Correct 16 ms 6732 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2792 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6848 KB Output is correct