oj.uz

Submission #1086694

# Submission time Handle Problem Language Result Execution time Memory
1086694 2024-09-11T09:27:57 Z _callmelucian Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

vector<int> s1, s2, s3, v1, v2, v3;
int ans = INT_MAX;

void btr (int cur) {
    if (cur == s1.size() + s2.size() + s3.size()) {
        int sum = 0;
        for (int i = 0; i < v1.size(); i++) sum += abs(v1[i] - s1[i]);
        for (int i = 0; i < v2.size(); i++) sum += abs(v2[i] - s2[i]);
        for (int i = 0; i < v3.size(); i++) sum += abs(v3[i] - s3[i]);
        return ans = min(ans, sum / 2), void();
    }

    if (v1.size() < s1.size()) {
        if (v1.empty() || v1.back() + 1 != cur) {
            v1.push_back(cur);
            btr(cur + 1);
            v1.pop_back();
        }
    }

    if (v2.size() < s2.size()) {
        if (v2.empty() || v2.back() + 1 != cur) {
            v2.push_back(cur);
            btr(cur + 1);
            v2.pop_back();
        }
    }

    if (v3.size() < s3.size()) {
        if (v3.empty() || v3.back() + 1 != cur) {
            v3.push_back(cur);
            btr(cur + 1);
            v3.pop_back();
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<char> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        if (s[i] == 'R') s1.push_back(i);
        else if (s[i] == 'G') s2.push_back(i);
        else if (s[i] == 'Y') s3.push_back(i);
    }
    btr(0);

    cout << (ans == INT_MAX ? -1 : ans);

    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'void btr(int)':
joi2019_ho_t3.cpp:17:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if (cur == s1.size() + s2.size() + s3.size()) {
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:19:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (int i = 0; i < v1.size(); i++) sum += abs(v1[i] - s1[i]);
      |                         ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < v2.size(); i++) sum += abs(v2[i] - s2[i]);
      |                         ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i = 0; i < v3.size(); i++) sum += abs(v3[i] - s3[i]);
      |                         ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 460 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 456 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -