Submission #497383

#	Time	Username	Problem	Language	Result	Execution time	Memory
497383		armashka	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	20 / 100	1085 ms	588 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e18;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            

ll n, ans = inf;
string s;
set <ll> a, b, c;
set <ll>::iterator it1, it2, it3;
vector <ll> pos;

void rec(string res) {
	if (res.sz == n) {

		for (int i = 1; i < res.sz; ++ i) {
			if (res[i] == res[i - 1]) return;
		}
		
		ll cnt = 0;
		for (int i = 0; i < pos.sz; ++ i) {
			for (int j = i + 1; j < pos.sz; ++ j) {
				if (pos[i] > pos[j]) ++ cnt;
			}
		}
		ans = min(ans, cnt);
		return;
	}
	if (res.empty()) {
		if (it1 != a.end()) {
			pos.pb(*it1);
			++ it1;
			rec(res + "R");
			pos.pop_back();
			-- it1;							    	
		}
		if (it2 != b.end()) {
			pos.pb(*it2);
			++ it2;
			rec(res + "G");
			pos.pop_back();
			-- it2;							    	
		}
		if (it3 != c.end()) {
			pos.pb(*it3);
			++ it3;
			rec(res + "Y");
			pos.pop_back();
			-- it3;							    	
		}
	} else {
		if (res.back() == 'R') {
        	if (it2 != b.end()) {
				pos.pb(*it2);
				++ it2;
				rec(res + "G");
				pos.pop_back();
				-- it2;							    	
			}
			if (it3 != c.end()) {
				pos.pb(*it3);
				++ it3;
				rec(res + "Y");
				pos.pop_back();
				-- it3;							    	
			}
		} else if (res.back() == 'Y') {
			if (it1 != a.end()) {
				pos.pb(*it1);
				++ it1;
				rec(res + "R");
				pos.pop_back();
				-- it1;							    	
			}
			if (it2 != b.end()) {
				pos.pb(*it2);
				++ it2;
				rec(res + "G");
				pos.pop_back();
				-- it2;							    	
			}
		} else {
            if (it1 != a.end()) {
				pos.pb(*it1);
				++ it1;
				rec(res + "R");
				pos.pop_back();
				-- it1;							    	
			}
			if (it3 != c.end()) {
				pos.pb(*it3);
				++ it3;
				rec(res + "Y");
				pos.pop_back();
				-- it3;							    	
			}
		}
	}
}

const void solve(/*Armashka*/) {
	cin >> n >> s;
	s = " " + s;
	for (int i = 1; i <= n; ++ i) {
		if (s[i] == 'R') a.insert(i);
		else if (s[i] == 'G') b.insert(i);
		else c.insert(i);
	}
	if (a.sz) it1 = a.begin();
	else it1 = a.end();
	if (b.sz) it2 = b.begin();
	else it2 = b.end();
	if (c.sz) it3 = c.begin();
	else it3 = c.end();
	rec("");
	if (ans == inf) ans = -1; 
	cout << ans << "\n";
}
            
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt --) {
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void rec(std::string)':
joi2019_ho_t3.cpp:38:13: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   38 |  if (res.sz == n) {
      |      ~~~~~~~^~~~
joi2019_ho_t3.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i = 1; i < res.sz; ++ i) {
      |                     ^
joi2019_ho_t3.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < pos.sz; ++ i) {
      |                     ^
joi2019_ho_t3.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for (int j = i + 1; j < pos.sz; ++ j) {
      |                          ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25