Submission #1086694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086694		_callmelucian	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	1 ms	460 KiB

joi2019_ho_t3

#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 (stderr)

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
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25