# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1107413 | vjudge1 | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++17 | 2 ms | 336 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) x.size()
#define pb push_back
#define F first
#define S second
#define nl '\n'
const int inf = 1e12;
bool ch( string s )
{
for( int i = 1; i < sz(s); ++i )
if( s[i] == s[i - 1] )
return false;
return true;
}
void solve()
{
int n;
string s;
cin >>n >>s;
map<char, int>cnt;
cnt['Y'] = cnt['R'] = cnt['G'] = 0;
vector< int >r, g;
int pr[n], pg[n];
pr[0] = pg[0] = 0;
for( int i = 0; i < n; ++i )
{
cnt[s[i]]++;
if( i > 0 )
{
pr[i] = pr[i - 1];
pg[i] = pg[i - 1];
}
if( s[i] == 'R' )
{
r.pb( i );
++pr[i];
}
if( s[i] == 'G' )
{
g.pb( i );
++pg[i];
}
}
int x = cnt['Y'];
int y = cnt['R'];
int z = cnt['G'];
if( x - 1 > y + z || y - 1 > x + z || z - 1 > x + y )
{
cout <<-1 <<nl;
return;
}
if( cnt['G'] + cnt['R'] == n )
{
if( cnt['G'] > cnt['R'] )
{
swap(cnt['R'], cnt['G']);
swap(r, g);
for( int i = 0; i < n; ++i )
swap(pr[i], pg[i]);
}
int ans = 0;
if( cnt['R'] > cnt['G'] )
{
int pos = 1;
for( int i: g )
{
ans += abs(pos - i);
pos += 2;
}
}
else
{
int cnt1 = 0, cnt2 = 0, pos = 0;
for( int i: r )
{
cnt1 += abs(i - pos);
pos += 2;
}
pos = 0;
for( int i: g )
{
cnt2 += abs(i - pos);
pos += 2;
}
ans = min(cnt1, cnt2);
}
cout <<ans <<nl;
return;
}
else
{
int ans = inf;
map<string, int>mp;
queue< string >q;
mp[s] = 0;
q.push(s);
while( !q.empty() )
{
string v = q.front();
q.pop();
if( ch(v) )
{
ans = min(ans, (int)mp[v]);
continue;
}
for( int i = 1; i < n; ++i )
{
string v1 = v;
swap(v1[i], v1[i - 1]);
if( !mp.count(v1) )
{
mp[v1] = mp[v] + 1;
q.push(v1);
}
}
}
cout <<ans;
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >>T;
while( T-- )
solve();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |