oj.uz

Submission #799107

# Submission time Handle Problem Language Result Execution time Memory
799107 2023-07-31T09:44:08 Z yeediot Type Printer (IOI08_printer) C++14
10 / 100
 26 ms 11060 KB 
#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);
    }
    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

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.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 8192 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 11060 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -