Submission #799108

#	Time	Username	Problem	Language	Result	Execution time	Memory
799108		yeediot	Type Printer (IOI08_printer)	C++14	10 / 100	30 ms	11064 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
const int mxn=25005;
const int mxlen=21;
const int mul=9973;
const int mod=1e9+7;
int h[mxn][mxlen];
int p[mxlen];
void hsh(string s,int id){
    for(int i=0;i<sz(s);i++){
        h[id][i+1]=((h[id][i]*mul)%mod+(s[i]-'a'+1))%mod;
    }
}
int get(int a,int b,int id){
    return ((h[id][b+1]-(h[id][a]*p[b-a+1])%mod)+mod)%mod;
}
bool cmp(pair<string,int> a,pair<string,int> b){
    if(sz(a.F)!=sz(b.F)){
        return sz(a.F)<sz(b.F);
    }
    int l=0,r=sz(a.F)-1;
    while(l<r){
        int mm=l+r+1>>1;
        if(get(0,mm,a.S)==get(0,mm,b.S)){
            l=mm;
        }
        else{
            r=mm-1;
        }
    }
    if(l==sz(a.F)-1){
        return true;
    }
    return a.F[l+1]<b.F[l+1];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector<pair<string,int>>s;
    for(int i=0;i<n;i++){
        string temp;
        cin>>temp;
        s.pb({temp,i});
        hsh(temp,i);
    }
    p[0]=1;
    for(int i=0;i<20;i++){
        p[i+1]=(p[i]*mul)%mod;
    }
    sort(all(s),cmp);
    string now="";
    vector<char>op;
    for(int i=0;i<n;i++){
        while(sz(now)>sz(s[i].F)){
            now.pop_back();
            op.pb('-');
        }
        while(sz(now) and now!=s[i].F.substr(0,sz(now))){
            now.pop_back();
            op.pb('-');
        }
        while(sz(now)<sz(s[i].F)){
            now+=s[i].F[sz(now)];
            op.pb(s[i].F[sz(now)-1]);
        }op.pb('P');
    }cout<<sz(op)<<'\n';
    for(auto i:op){
        cout<<i<<'\n';
    }
}
 /*
 input:
 
 */

Compilation message (stderr)

printer.cpp: In function 'bool cmp(std::pair<std::__cxx11::basic_string<char>, long long int>, std::pair<std::__cxx11::basic_string<char>, long long int>)':
printer.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mm=l+r+1>>1;
      |                ~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10