Submission #1779792


Source Code Expand

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"

using namespace std;
typedef long long int ll;

#define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}}
#define ALL(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(auto cnt=0ll;(cnt)<(l);++(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
#define EPS 1e-12
template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
template<typename iterator> inline size_t argmin(iterator begin, iterator end) { return distance(begin, min_element(begin, end)); }
template<typename iterator> inline size_t argmax(iterator begin, iterator end) { return distance(begin, max_element(begin, end)); }
template<typename T> T& maxset(T& to, const T& val) { return to = max(to, val); }
template<typename T> T& minset(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(0); }
mt19937_64 randdev(8901016);
inline ll rand_range(ll l, ll h) {
    return uniform_int_distribution<ll>(l, h)(randdev);
}

#ifdef __MAI
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
#ifdef __VSCC
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#endif
namespace {
#define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E)
    class MaiScanner {
    public:
        template<typename T> void input_integer(T& var) {
            var = 0;
            T sign = 1;
            int cc = getchar_unlocked();
            for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
                if (cc == '-') sign = -1;
            for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
                var = (var << 3) + (var << 1) + cc - '0';
            var = var*sign;
        }
        inline int c() { return getchar_unlocked(); }
        inline MaiScanner& operator>>(int& var) {
            input_integer<int>(var);
            return *this;
        }
        inline MaiScanner& operator>>(long long& var) {
            input_integer<long long>(var);
            return *this;
        }
        inline MaiScanner& operator>>(string& var) {
            int cc = getchar_unlocked();
            for (; !isvisiblechar(cc); cc = getchar_unlocked());
            for (; isvisiblechar(cc); cc = getchar_unlocked())
                var.push_back(cc);
            return *this;
        }
        template<typename IT> void in(IT begin, IT end) {
            for (auto it = begin; it != end; ++it) *this >> *it;
        }
    };
}
MaiScanner scanner;


ll m, n, kei;
string str;

int main() {

    scanner >> str;
    n = str.size();

    vector<int> next(n, -1);
    {
        vector<int> last(30, -1);
        repeat(i, n) {
            int c = str[i] - 'a';
            if (last[c] >= 0)
                next[last[c]] = i;
            last[c] = i;
        }
    }
    vector<int> div(n);
    vector<int> cnt(30);

    for (int i = n - 1; 0 <= i; --i) {
        int c = str[i] - 'a';
        int b = 1;
        cnt[c]++;
        repeat(j, 'z' - 'a' + 1)
            b &= !!cnt[j];

        if (b) {
            div[i] += 1;
            // repeat(j, 'z' - 'a' + 1)
            // if (cnt[j] == 1) {
            //     ans.push_back(j + 'a');
            //     break;
            // }
            fill(ALL(cnt), 0);
        }
    }
    iterate(i, 1, n)
        div[i] += div[i - 1];

    string ans(div[n-1]+1, 'z'+1);
    //repeat(j, 'z' - 'a' + 1)
    //    if (cnt[j] == 0) {
    //        ans.push_back(j + 'a');
    //        break;
    //    }
    repeat(i, n) {
        int c = str[i] - 'a';
        if (next[i] > 0 && div[i] == div[next[i]] - 1) {
            //putchar(str[i]);
            minset(ans[div[i - 1]], str[i]);
        }
    }
    debugv(div)
    
    cout << ans << endl;


    return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User m_buyoh
Language Text (cat)
Score 0
Code Size 4418 Byte
Status WA
Exec Time 1 ms
Memory 128 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
WA × 3
WA × 36
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 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 WA 1 ms 128 KB
10.txt WA 1 ms 128 KB
11.txt WA 1 ms 128 KB
12.txt WA 1 ms 128 KB
13.txt WA 1 ms 128 KB
14.txt WA 1 ms 128 KB
15.txt WA 1 ms 128 KB
16.txt WA 1 ms 128 KB
17.txt WA 1 ms 128 KB
18.txt WA 1 ms 128 KB
19.txt WA 1 ms 128 KB
2.txt WA 1 ms 128 KB
20.txt WA 1 ms 128 KB
21.txt WA 1 ms 128 KB
22.txt WA 1 ms 128 KB
23.txt WA 1 ms 128 KB
24.txt WA 1 ms 128 KB
25.txt WA 1 ms 128 KB
26.txt WA 1 ms 128 KB
27.txt WA 1 ms 128 KB
28.txt WA 1 ms 128 KB
29.txt WA 1 ms 128 KB
3.txt WA 1 ms 128 KB
30.txt WA 1 ms 128 KB
4.txt WA 1 ms 128 KB
5.txt WA 1 ms 128 KB
6.txt WA 1 ms 128 KB
7.txt WA 1 ms 128 KB
8.txt WA 1 ms 128 KB
9.txt WA 1 ms 128 KB
sample1.txt WA 1 ms 128 KB
sample2.txt WA 1 ms 128 KB
sample3.txt WA 1 ms 128 KB