oj.uz

Submission #1089257

# Submission time Handle Problem Language Result Execution time Memory
1089257 2024-09-16T08:20:10 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
20 / 100
 500 ms 476 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back	
#define pob pop_back
#define int long long
#define int2 __int128_t
#define Shrek_Crush228 ios_base::sync_with_stdio(0), cin.tie(0);
#define F first
#define S second
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define nep next_permutation
#define sigma signed
#define pii pair <int, int> 

using namespace std;

string alp = "abcdefghijklmnopqrstuvwxyz";
string ae = "aoeiuy";
string nums = "123456789";

const int N = 1e5 + 123;
const int inf = 1e18;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353;
const long long maxsum = 1e14;

int a[N], b[N], c[N], l, r, n, k, m, w, sum, sum1, y, ans1, mx = -inf, mn = inf, ind, ind1, pref[N], suf[N];
string s1, t;
ll ans, x;

template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct RT
{
	int sum, l, r, ind;	
};
int gcd( int a, int b )
{
	return ( b ? gcd( b, a % b ) : a );
}
int lcm( int a, int b )
{
	return a / gcd( a, b ) * b;
}
int bp( int a, int b, int m )
{
	if( !b ) return 1;
	if( b & 1 ) return bp( a, b >> 1, m ) * bp( a, b >> 1, m ) % m * a % m;
	else return bp( a, b >> 1, m ) * bp( a, b >> 1, m ) % m;
}
struct po
{
	int mn, sum, mx;
};
int xr, xg, xy;

void rec( int ind = 0, int cntr = 0, int cntg = 0, int cnty = 0, string ss = "" )
{
	if( ind == n )
	{
		int rr, res = 0, ok = 1;
		
		FOR( i, 1, n - 1, 1 )
		{
			if( ss[i] == ss[i - 1] ) ok = 0;
		}
		if( !ok ) return;
		string s = s1;
		
		FOR( i, 0, n - 1, 1 )
		{
			rr = i;
			
			while( s[rr] != ss[i] && rr < n ) rr ++;
			if( rr == n ) break;
			
			while( rr > i ) swap( s[rr], s[rr - 1] ), rr --, res ++;  
		}
		if( ans > res ) ans = res, t = ss;  
		return;
	}
	if( cntr + 1 <= xr ) rec( ind + 1, cntr + 1, cntg, cnty, ss + 'R' );
	if( cntg + 1 <= xg ) rec( ind + 1, cntr, cntg + 1, cnty, ss + 'G' );
	if( cnty + 1 <= xy ) rec( ind + 1, cntr, cntg, cnty + 1, ss + 'Y' );
}
int calc( int xr, int xg, string s )
{
	int tp, res = 0;
	if( xr == xg - 1 ) tp = 1;
	else if( xg == xr - 1 ) tp = 0;
		
	FOR( nw, 0, n - 1, 1 )
	{
		char ch;
		if( tp == 0 ) ch = 'R';
		else ch = 'G';
		int i = nw;
		
		while( s[i] != ch && i < n ) i ++;
		if( i == n ) break;
		while( i != nw ) swap( s[i], s[i - 1] ), i --, res ++;
		tp ^= 1;
	}
	return res;
}
void solve()
{
	cin >> n >> s1;
	
	FOR( i, 0, n - 1, 1 )
	{
		if( s1[i] == 'R' ) xr ++;
		if( s1[i] == 'G' ) xg ++;
		if( s1[i] == 'Y' ) xy ++;
	}
	if( xy == 0 )
	{
		if( abs( xr - xg ) > 1 ) 
		{
			cout << -1;
			return;
		}
		if( xr == xg ) ans = min( calc( xr - 1, xg, s1 ), calc( xr, xg - 1, s1 ));
		else ans = calc( xr, xg, s1 );
		
		cout << ans;
		return;
	}
	ans = inf;
	rec();
	cout << ( ans == inf ? -1 : ans );// << '\n' << t;
}
sigma main() 
{
	//freopen("rmq.in", "r", stdin);
	//freopen("rmq.out", "w", stdout);
	    
    Shrek_Crush228	
    
    int test = 1;
    
    if( !test ) cin >> test;
	
	while( test -- )
	{
		solve();
	}
}
// solved by KluydQ

Compilation message

joi2019_ho_t3.cpp: In function 'long long int calc(long long int, long long int, std::string)':
joi2019_ho_t3.cpp:117:6: warning: 'tp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |   tp ^= 1;
      |   ~~~^~~~

Subtask #1
5.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 1 ms 348 KB Output is correct
5 Correct 18 ms 476 KB Output is correct
6 Correct 31 ms 348 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 35 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 18 ms 348 KB Output is correct
12 Correct 51 ms 348 KB Output is correct
13 Correct 10 ms 352 KB Output is correct
14 Correct 8 ms 348 KB Output is correct
15 Correct 23 ms 476 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

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 1 ms 348 KB Output is correct
5 Correct 18 ms 476 KB Output is correct
6 Correct 31 ms 348 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 35 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 18 ms 348 KB Output is correct
12 Correct 51 ms 348 KB Output is correct
13 Correct 10 ms 352 KB Output is correct
14 Correct 8 ms 348 KB Output is correct
15 Correct 23 ms 476 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Execution timed out 1035 ms 348 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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 1 ms 348 KB Output is correct
5 Correct 18 ms 476 KB Output is correct
6 Correct 31 ms 348 KB Output is correct
7 Correct 22 ms 344 KB Output is correct
8 Correct 35 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 18 ms 348 KB Output is correct
12 Correct 51 ms 348 KB Output is correct
13 Correct 10 ms 352 KB Output is correct
14 Correct 8 ms 348 KB Output is correct
15 Correct 23 ms 476 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Execution timed out 1035 ms 348 KB Time limit exceeded
19 Halted 0 ms 0 KB -