Submission #3196301


Source Code Expand

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template<typename T>
ostream& operator << (ostream& os, vector<T> v)
{
  os << "(";
  each (i, v) os << i << ",";
  os << ")";
  return os;
}

const int N = 2 * 1e5 + 5;
const int M = 'z' + 5;
int g[N][M];

const int inf = 1 << 28;
int memo[N];
int path[N];
int rec(int curr)
{
  int& ret = memo[curr];
  if (ret != -1) return ret;

  int mn = inf;
  for (char c = 'a'; c <= 'z'; ++c) {
    if (!g[curr][c]) {
      path[curr] = -1 * int(c);
      return ret = 0;
    }
    int len = rec(g[curr][c]) + 1;
    if (len < mn) {
      mn = len;
      path[curr] = g[curr][c];
    }
  }
  return ret = mn;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  string s;
  while (cin >> s) {
    s = "@" + s;

    fill(&g[0][0], &g[N - 1][M - 1] + 1, 0);
    for (int i = s.size() - 2; 0 <= i; --i) {
      for (char c = 'a'; c <= 'z'; ++c) {
        g[i][c] = g[i + 1][c];
      }
      g[i][s[i + 1]] = i + 1;
    }

    fill(memo, memo + N, -1);
    fill(path, path + N, -1);
    rec(0);
    string t;
    for (int i = 0; ; i = path[i]) {
      if (i < 0) {
        t += abs(i);
        break;
      }
      t += s[i];
    }
    cout << t.substr(1) << endl;
  }

  return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User Johniel
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1655 Byte
Status AC
Exec Time 70 ms
Memory 101712 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 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 AC 31 ms 100992 KB
10.txt AC 69 ms 101712 KB
11.txt AC 69 ms 101712 KB
12.txt AC 69 ms 101712 KB
13.txt AC 69 ms 101712 KB
14.txt AC 69 ms 101712 KB
15.txt AC 69 ms 101712 KB
16.txt AC 69 ms 101712 KB
17.txt AC 69 ms 101712 KB
18.txt AC 70 ms 101712 KB
19.txt AC 70 ms 101712 KB
2.txt AC 31 ms 100992 KB
20.txt AC 69 ms 101712 KB
21.txt AC 69 ms 101712 KB
22.txt AC 69 ms 101712 KB
23.txt AC 70 ms 101712 KB
24.txt AC 69 ms 101712 KB
25.txt AC 68 ms 101712 KB
26.txt AC 67 ms 101712 KB
27.txt AC 68 ms 101712 KB
28.txt AC 68 ms 101712 KB
29.txt AC 68 ms 101712 KB
3.txt AC 32 ms 101120 KB
30.txt AC 60 ms 101712 KB
4.txt AC 32 ms 101120 KB
5.txt AC 51 ms 101356 KB
6.txt AC 51 ms 101356 KB
7.txt AC 69 ms 101712 KB
8.txt AC 69 ms 101712 KB
9.txt AC 69 ms 101712 KB
sample1.txt AC 31 ms 100992 KB
sample2.txt AC 31 ms 100992 KB
sample3.txt AC 31 ms 100992 KB