Submission #2998694


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


int cmp(const void *p, const void *q) {
    // printf("(%s) (%s)\n", *(const char **)p, *(const char **)q);
    return strcmp(*(const char **)p, *(const char **)q);
}

string solve(string& A) {
    int L = A.size();
    vvi az(26);
    rep(i,L) {
        int ch = A[i] - 'a';
        az[ch].pb(i);
    }
#ifdef DEBUG
    rep(ch,26){
        cerr << (char)('a'+ch) << " " << az[ch] << endl;
    }
#endif

    vector<int> rev(L);
    set<int> abc;
    int k = 0;
    for (int i=L-1; i>=0; --i) {
        abc.insert(A[i] - 'a');
        rev[i] = k;
        if (abc.size() == 26) {
            ++k;
            abc.clear();
        }
    }
#ifdef DEBUG
    cerr << rev << endl;
#endif
    int len = k+1;

    vector<char> ans(len);
    rep(ch,26) {
        if (!found(abc, ch)) {
            ans[0] = ch;
            if (az[ch].empty()) {
                ans[0] += 'a';
                return string(ALL(ans));
            }
            break;
        }
    }

    int last = az[ans[0]][0];
    // cerr << last << endl;
    rep1(i,k) {
        rep(ch,26) {
            auto it = lower_bound(ALL(az[ch]), last+1);
            if (it != az[ch].end()) {
                int at = *it;
                if (rev[last]-1 != rev[at]) continue;
                last = at;
            }
            ans[i] = ch; break;
        }
    }

    rep(i, len) ans[i] += 'a';
    return string(ALL(ans));
}

int main() {
    string A; cin >> A;
    cout << solve(A) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User naoya_t
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2755 Byte
Status
Exec Time 25 ms
Memory 2180 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 600 / 600 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 1 ms 256 KB
10.txt 19 ms 2180 KB
11.txt 19 ms 2180 KB
12.txt 19 ms 2180 KB
13.txt 19 ms 2180 KB
14.txt 19 ms 2180 KB
15.txt 19 ms 2052 KB
16.txt 19 ms 2180 KB
17.txt 21 ms 2180 KB
18.txt 21 ms 2180 KB
19.txt 23 ms 2180 KB
2.txt 1 ms 256 KB
20.txt 24 ms 2180 KB
21.txt 24 ms 2180 KB
22.txt 24 ms 2180 KB
23.txt 25 ms 2180 KB
24.txt 16 ms 2180 KB
25.txt 15 ms 2180 KB
26.txt 14 ms 2180 KB
27.txt 14 ms 2180 KB
28.txt 14 ms 2180 KB
29.txt 14 ms 2180 KB
3.txt 2 ms 384 KB
30.txt 14 ms 2180 KB
4.txt 2 ms 384 KB
5.txt 10 ms 1280 KB
6.txt 10 ms 1152 KB
7.txt 19 ms 2180 KB
8.txt 19 ms 2180 KB
9.txt 19 ms 2052 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB