oj.uz

Submission #783153

# Submission time Handle Problem Language Result Execution time Memory
783153 2023-07-14T16:04:39 Z Matblube Type Printer (IOI08_printer) C++14
100 / 100
 53 ms 17104 KB 
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
#define fr(i, x) for(ll i=0 ; i<x ; i++)
#define fra(x, v) for(auto x:v)
#define fra1(x,v) for(auto && x:v)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define pb(x) push_back(x)
#define F first
#define S second
#define inf 10000000000
#define sz(x) (ll) x.size()

const double PI=acos(-1);
const ll MOD=1e9+7, maxN=100010;

struct uwu{
    ll x ,y, z;
};

ll gcd(ll a, ll b){return (!b)?a:(gcd(b, a%b));}

ll lcm(ll a, ll b){
    if(a>b) swap(a, b);
    return a/gcd(a, b)*b;
}

ll binpow(ll a, ll b){
    ll cc=1;
    while(b){
        if(b&1) cc*=a;
        a*=a;
        b>>=1;
    }
    return cc;
}
ll binpow1(ll a, ll b){
    ll cc=1;
    while(b){
        if(b&1) cc=cc*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return cc%MOD;
}

ll arr[50][50], n, m;
ll dp[50][50];

void move(ll a, ll b){
    for(ll i=a ; i<=n ; i++){
        for(ll j=b ; j<=m ; j++){
            dp[i][j]+=(max(dp[i-1][j], dp[i][j-1]));
        }
    }
}

ll subs(string a, string b){
    if(a.size()>b.size()) swap(a, b);
    ll i=0;
    while(i<a.size() && i<b.size() && a[i]==b[i]) i++;
    return i;
}

bool comp(string a, string b){
    return a.size()<b.size();
}

// ordenar lexicograficamente
//tener los caracteres de las palabras mas largas al final de cada string
void sortString(ll x, ll y, ll n, string a, vector<string>&v){
    if(y-x<2) return;
    vector<string>s[26];
    string aux="";
    char uwu;
    for(ll i=x ; i<y ; i++){
        if(sz(v[i])==n){
            aux=v[i]; continue;
        }
        uwu=v[i][n];
        s[uwu-'a'].pb(v[i]);
    }
    ll xd=x, pro;
    if(aux.size()) v[xd++]=aux;
    fr(i, 26){
        if(i==a[n]-'a') continue;
        pro=xd;
        fra1(nosebro,s[i]) v[xd++]=nosebro;
        sortString(pro, xd, n+1, a, v);
    }
    pro=xd;
    fra1(nosebro, s[a[n]-'a']) v[xd++]=nosebro;
    sortString(pro, xd, n+1, a, v);
}

void solve(){
    ll n, aux; cin>>n;
    vector<string>v(n);
    string xdxd;
    fra1(x, v){
        cin>>x;
        if(x.size()>xdxd.size()) xdxd=x;
    }
    sortString(0, n, 0, xdxd, v);
//    fra(x, v) cout<<x<<"\n";
    string a, b;
    a=b="";
    fra(x, v){
        aux=subs(a, x);
        while(a.size()>aux){
            a.pop_back();
            b.push_back('-');
        }
        a+=x.substr(aux);
        b+=x.substr(aux);
        b.push_back('P');
    }
    cout<<b.size()<<"\n";
    fra(x, b) cout<<x<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Compilation message

printer.cpp: In function 'll subs(std::string, std::string)':
printer.cpp:77:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while(i<a.size() && i<b.size() && a[i]==b[i]) i++;
      |           ~^~~~~~~~~
printer.cpp:77:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     while(i<a.size() && i<b.size() && a[i]==b[i]) i++;
      |                         ~^~~~~~~~~
printer.cpp: In function 'void solve()':
printer.cpp:126:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  126 |         while(a.size()>aux){
      |               ~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 8 ms 1364 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1492 KB Output is correct
2 Correct 21 ms 1996 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3420 KB Output is correct
2 Correct 44 ms 6220 KB Output is correct
3 Correct 38 ms 15172 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2204 KB Output is correct
2 Correct 53 ms 6604 KB Output is correct
3 Correct 44 ms 17104 KB Output is correct
4 Correct 48 ms 6988 KB Output is correct