oj.uz

Submission #367361

# Submission time Handle Problem Language Result Execution time Memory
367361 2021-02-16T23:53:40 Z lookcook Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
5 / 100
 500 ms 104868 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

int dp[3][70][70][70][70]; // 0 = r, 1 = g, 2 = y
int n;
vector<int> r, g, y;
string s;

int rec(int pos, int rp, int gp, int yp, int lst) {
    if (pos == n) return 0;
    if (dp[lst][pos][rp][gp][yp] != -1) return dp[lst][pos][rp][gp][yp];
    int res = 1e15;
    if (r.size()!=rp && lst!=0) res = min(res, rec(pos+1, rp+1, gp, yp, 0) + abs(r[rp]-pos));
    if (g.size()!=gp && lst!=1) res = min(res, rec(pos+1, rp, gp+1, yp, 1) + abs(g[gp]-pos));
    if (y.size()!=yp && lst!=2) res = min(res, rec(pos+1, rp, gp, yp+1, 2) + abs(y[yp]-pos));
    dp[lst][pos][rp][gp][yp] = res;
    return res;
}

int fast() {
    r = {}, g = {}, y = {};
    for (int i = 0; i < 3; i++)
        for (int a = 0; a < 70; a++)
            for (int b = 0; b < 70; b++)
                for (int c = 0; c < 70; c++)
                    for (int d = 0; d < 70; d++)
                        dp[i][a][b][c][d] = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') r.push_back(i);
        if (s[i] == 'G') g.push_back(i);
        if (s[i] == 'Y') y.push_back(i);
    }
    int res = min(rec(0,0,0,0,1),rec(0,0,0,0,0));
    if (res >= 1e15) return -1;
    else return res/2;
}

int slow() {
    queue<pair<string,int>> q;
    q.push({s,0});
    set<string> vis;
    vis.insert(s);
    while (!q.empty()) {
        pair<string,int> p = q.front();
        q.pop();
        bool ok = true;
        for (int i = 1; i < s.length(); i++) {
            if (p.first[i] == p.first[i-1]) {
                ok = false;
            }
        }
        if (ok) return p.second;
        for (int i = 1; i < p.first.length(); i++) {
            string t = p.first;
            swap(t[i],t[i-1]);
            if (vis.count(t) == 0) {
                vis.insert(t);
                q.push({t,p.second+1});
            }
        }
    }
    return -1;
}

char a[8];
void gen(int x) {
    if (x == n) {
        s = "";
        for (int i = 0; i < n; i++) s += a[i];
        int fa = fast();
        int sl = slow();
        if (fa != sl) {
            cout << "WA, fast=" << fa << " slow=" << sl << '\n';
            cout << s << '\n';
        }
        return;
    }
    a[x] = 'R';
    gen(x+1);
    a[x] = 'G';
    gen(x+1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    cout << slow() << '\n';
}

Compilation message

joi2019_ho_t3.cpp: In function 'long long int rec(long long int, long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:16:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   16 |     if (r.size()!=rp && lst!=0) res = min(res, rec(pos+1, rp+1, gp, yp, 0) + abs(r[rp]-pos));
      |         ~~~~~~~~^~~~
joi2019_ho_t3.cpp:17:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   17 |     if (g.size()!=gp && lst!=1) res = min(res, rec(pos+1, rp, gp+1, yp, 1) + abs(g[gp]-pos));
      |         ~~~~~~~~^~~~
joi2019_ho_t3.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   18 |     if (y.size()!=yp && lst!=2) res = min(res, rec(pos+1, rp, gp, yp+1, 2) + abs(y[yp]-pos));
      |         ~~~~~~~~^~~~
joi2019_ho_t3.cpp: In function 'long long int slow()':
joi2019_ho_t3.cpp:50:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 1; i < s.length(); i++) {
      |                         ~~^~~~~~~~~~~~
joi2019_ho_t3.cpp:56:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 1; i < p.first.length(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 93 ms 3308 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 10 ms 876 KB Output is correct
8 Correct 9 ms 876 KB Output is correct
9 Correct 67 ms 2156 KB Output is correct
10 Correct 9 ms 620 KB Output is correct
11 Correct 128 ms 4076 KB Output is correct
12 Correct 39 ms 1772 KB Output is correct
13 Correct 403 ms 8428 KB Output is correct
14 Correct 47 ms 1644 KB Output is correct
15 Correct 7 ms 620 KB Output is correct
16 Correct 16 ms 748 KB Output is correct
17 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 93 ms 3308 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 10 ms 876 KB Output is correct
8 Correct 9 ms 876 KB Output is correct
9 Correct 67 ms 2156 KB Output is correct
10 Correct 9 ms 620 KB Output is correct
11 Correct 128 ms 4076 KB Output is correct
12 Correct 39 ms 1772 KB Output is correct
13 Correct 403 ms 8428 KB Output is correct
14 Correct 47 ms 1644 KB Output is correct
15 Correct 7 ms 620 KB Output is correct
16 Correct 16 ms 748 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Execution timed out 1101 ms 104868 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 1080 ms 7412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 93 ms 3308 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 10 ms 876 KB Output is correct
8 Correct 9 ms 876 KB Output is correct
9 Correct 67 ms 2156 KB Output is correct
10 Correct 9 ms 620 KB Output is correct
11 Correct 128 ms 4076 KB Output is correct
12 Correct 39 ms 1772 KB Output is correct
13 Correct 403 ms 8428 KB Output is correct
14 Correct 47 ms 1644 KB Output is correct
15 Correct 7 ms 620 KB Output is correct
16 Correct 16 ms 748 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Execution timed out 1101 ms 104868 KB Time limit exceeded
19 Halted 0 ms 0 KB -