oj.uz

Submission #885104

# Submission time Handle Problem Language Result Execution time Memory
885104 2023-12-09T02:31:10 Z VN_AnhTuan Periodicity (POI11_okr) C++17
100 / 100
 32 ms 10468 KB 
//  Author : Nguyen Anh Tuan - THPT Chuyen Bac Giang - Train VOI 2023/2024

#include<bits/stdc++.h>
#define file(NAME) {freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout);}
#define foru(i, a, b) for(int i=(a);i<=(b);i++)
#define ford(i, a, b) for(int i=(a);i>=(b);i--)
#define rep(i, n) for(int i=(1);i<=(n);i++)
#define fi first
#define se second
#define mp make_pair
#define SZ(v) ((int)((v).size()))
#define all(v) v.begin(),v.end()
#define RR(X) X.resize(unique(all(X)) - begin(X))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;

namespace IO
{
    #define getchar() (ipos==iend and (iend=(ipos=_ibuf)+fread(_ibuf,1,__bufsize,stdin),ipos==iend)?EOF:*ipos++)
    #define putchar(ch) (opos==oend?fwrite(_obuf,1,__bufsize,stdout),opos=_obuf:0,*opos++=(ch))
    #define __bufsize (1<<20)
    char _ibuf[__bufsize],_obuf[__bufsize],_stk[20];
    char *ipos=_ibuf,*iend=_ibuf,*opos=_obuf,*oend = _obuf+__bufsize,*stkpos = _stk;
    struct END{~END(){fwrite(_obuf,1,opos-_obuf,stdout);}}__;
    inline void read(int &x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void write(int x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
    inline void lread(ll&x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void lwrite(ll x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
};

void maximum(ll &a, ll b) {if(b > a) a = b;}
void minimum(ll &a, ll b) {if(b < a) a = b;}
bool bit(int x, int i) {return (x >> i) & 1;}

//-----------------------------------------------------------------------------------
//      END OF TEMPLATE
//-----------------------------------------------------------------------------------
//      Nguyen Anh Tuan - AnhTuan_BG
//      PRAY FOR VOI 2023
//-----------------------------------------------------------------------------------

vector<int> extract(string s, int n)
{
    vector<int> pi(n);
    pi[0] = 0;
    foru(i, 1, n - 1)
    {
        int j = pi[i-1];
        while(j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    vector<int> borders;
    int j = n;
    while(j > 0)
    {
        borders.push_back(j);
        j = pi[j - 1];
    }
    reverse(borders.begin(), borders.end());
    return borders;
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //file("");

    int t;
    cin >> t;
    rep(TEST, t)
    {
        string s;
        cin >> s;
        int n = s.size();
        vector<int> p = extract(s,n);
        char ans[n + 1];
        if(p[0] == 1) ans[0] = '0';
        else foru(i, 0, p[0] - 1) ans[i] = '0' + (i == p[0] - 1);

        foru(i, 1, p.size() - 1)
        {
            if(p[i] - 2 * p[i-1] <= 0)
                memcpy(ans + p[i-1], ans + 2 * p[i-1] - p[i], sizeof(char) * (p[i] - p[i-1]));
            else
            {
                for(int j = p[i - 1]; j < p[i] - p[i - 1]; j++)
                    ans[j] = '0';
                memcpy(ans + p[i] - p[i-1], ans, sizeof(char) * p[i - 1]);
                vector<int> border_now = extract(ans, p[i]);
                if (!equal(p.begin(), p.begin()+i+1, border_now.begin()))
                    ans[p[i] - p[i-1] - 1] = '1';
            }
        }
        ans[n] = 0;
        cout << ans << "\n";
    }

    return 0;
}

Compilation message

okr.cpp: In function 'void IO::read(int&)':
okr.cpp:31:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |         register ll f=0,ch;
      |                     ^
okr.cpp:31:25: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |         register ll f=0,ch;
      |                         ^~
okr.cpp: In function 'void IO::lread(ll&)':
okr.cpp:44:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |         register ll f=0,ch;
      |                     ^
okr.cpp:44:25: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |         register ll f=0,ch;
      |                         ^~
okr.cpp: In function 'int main()':
okr.cpp:5:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define foru(i, a, b) for(int i=(a);i<=(b);i++)
      |                                      ^
okr.cpp:108:9: note: in expansion of macro 'foru'
  108 |         foru(i, 1, p.size() - 1)
      |         ^~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
17.0 / 17.0

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

Subtask #5
17.0 / 17.0

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

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10468 KB Output is correct