oj.uz

Submission #915737

# Submission time Handle Problem Language Result Execution time Memory
915737 2024-01-24T15:58:28 Z ByeWorld Gondola (IOI14_gondola) C++14
100 / 100
 52 ms 9316 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define bupol __builtin_popcount
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+10;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+9;
const int SQRT = 520;
const int INF = 1e9+10;
typedef pair<ll,ll> pii;
typedef pair<int, pii> ipii;

ll sum(ll a, ll b){
	return (a+b)%MOD;
}
ll mul(ll a, ll b){
	a %= MOD; b %= MOD;
	return (1ll*a*b)%MOD;
}
ll expo(ll a, ll b){
	if(b==0) return 1ll;
	ll te = expo(a, b/2); te = mul(te, te);
	return (b%2==1 ? mul(te, a) : te);
}
int n;
int a[MAXN], sta[MAXN], idx = -1;
vector <int> vec, ans; vector <pii> sw;
map<int, bool> use;
int mn = INF, mx = -1;
ll ANS;

int valid(int N, int inputSeq[])
{
	n = N;
	for(int i=1; i<=n; i++) a[i] = inputSeq[i-1];

	for(int i=1; i<=n; i++){
		if(mn > a[i]){
			mn = a[i]; idx = i;
		}
	}
	assert(idx != -1); 
	vec.pb(-1);
	for(int i=idx; i<=n; i++) vec.pb(a[i]);
	for(int i=1; i<=idx-1; i++) vec.pb(a[i]);

	for(int i=1; i<=n; i++){
		if(use[vec[i]]) return 0; // ngedobel
		use[vec[i]] = 1;

		if(vec[i] >= n+1) continue; // gpp gk dicek
 		
 		// vec[i] <= n
 		ll num = vec[1]+i-1; // harusnya angkanya brp
 		if(num >= n+1) num -= n;

		if(mx >= vec[i] || vec[i] != num) return 0; // loh kok turun
		mx = max(mx, vec[i]);
		//cout << i << " p\n";
	}
 	return 1;
}

//----------------------

int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
	n = N;
	for(int i=1; i<=n; i++) a[i] = gondolaSeq[i-1];
 	for(int i=1; i<=n; i++){
		if(mn > a[i]){
			mn = a[i]; idx = i;
		}
	}
	assert(idx != -1); 
	vec.pb(-1);
	for(int i=idx; i<=n; i++) vec.pb(a[i]);
	for(int i=1; i<=idx-1; i++) vec.pb(a[i]);

	if(mn <= n){
		for(int i=1; i<=n; i++){
			if(use[vec[i]]) return 0; // ngedobel
			use[vec[i]] = 1;

	 		ll num = vec[1]+i-1; // harusnya angkanya brp
	 		if(num >= n+1) num -= n;
	 		sta[i] = num; // startnya brp

			if(vec[i] <= n) continue; // gpp gk dicek
			if(vec[i] >= n+1){
				sw.pb({vec[i], i});
			}
		}
	} else {
		for(int i=1; i<=n; i++){
			sta[i] = i;
			sw.pb({vec[i], i});
		}
	}
	sort(sw.begin(), sw.end());
	//for(auto in : sw) cout << vec[in.fi] << ' ' << in.se << " p\n";

	int cnt = n+1;
	for(auto in : sw){
		int idx = in.se, val = in.fi; // num -> val

		ans.pb(sta[idx]); sta[idx] = cnt++;
		for(int i=sta[idx]; true; i++){
			if(sta[idx]==val) break;
			ans.pb(sta[idx]);
			sta[idx] = cnt++;
		}
	}

	for(int i=0; i<ans.size(); i++) replacementSeq[i] = ans[i];
 	return (int)(ans.size());
}

//----------------------

int countReplacement(int N, int inputSeq[])
{
	if(!valid(N, inputSeq)) return 0;
	vec.clear(); mn = INF; mx = -1; use.clear();
	//cout << " masuk\n";
	n = N;
	for(int i=1; i<=n; i++) a[i] = inputSeq[i-1];

 	for(int i=1; i<=n; i++){
		if(mn > a[i]){
			mn = a[i]; idx = i;
		}
	}
	assert(idx != -1); 
	vec.pb(-1);
	for(int i=idx; i<=n; i++) vec.pb(a[i]);
	for(int i=1; i<=idx-1; i++) vec.pb(a[i]);

	ANS = 1ll;
//cout << " xx\n";
	if(mn <= n){
		for(int i=1; i<=n; i++){
	 		ll num = vec[1]+i-1; // harusnya angkanya brp
	 		if(num >= n+1) num -= n;
	 		sta[i] = num; // startnya brp

			if(vec[i] <= n) continue; // gpp gk dicek
			if(vec[i] >= n+1){
				sw.pb({vec[i], i});
			}
		}
	} else {
		for(int i=1; i<=n; i++){
			sta[i] = i;
			sw.pb({vec[i], i}); 
		}
		ANS = n;
	}
	sort(sw.begin(), sw.end());
	//for(auto in : sw) cout << in.fi << ' ' << in.se << " p\n";

	ll cnt = n, num = (ll)(sw.size());
	for(auto in : sw){
		ll idx = in.se, val = in.fi; // num -> val

		ANS = mul(ANS, expo(num, val-cnt-1));
		sta[idx] = val;
		cnt = val;
		// for(int i=sta[idx]; true; i++){
		// 	if(sta[idx]==val) break;
		// 	sta[idx] = cnt++;
		// }
		num--;
	}

	return (int)(ANS);
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=0; i<ans.size(); i++) replacementSeq[i] = ans[i];
      |               ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 10 ms 4792 KB Output is correct
7 Correct 8 ms 3796 KB Output is correct
8 Correct 20 ms 6604 KB Output is correct
9 Correct 6 ms 3672 KB Output is correct
10 Correct 24 ms 7368 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 10 ms 4636 KB Output is correct
7 Correct 8 ms 3800 KB Output is correct
8 Correct 26 ms 6612 KB Output is correct
9 Correct 6 ms 3676 KB Output is correct
10 Correct 24 ms 7480 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 4 ms 3164 KB Output is correct
14 Correct 1 ms 2492 KB Output is correct
15 Correct 8 ms 3796 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2596 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2492 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2476 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2592 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2496 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 2804 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 27 ms 7380 KB Output is correct
12 Correct 26 ms 7888 KB Output is correct
13 Correct 22 ms 6220 KB Output is correct
14 Correct 23 ms 7392 KB Output is correct
15 Correct 22 ms 6228 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2492 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 35 ms 7116 KB Output is correct
10 Correct 28 ms 6872 KB Output is correct
11 Correct 11 ms 4216 KB Output is correct
12 Correct 18 ms 4596 KB Output is correct
13 Correct 4 ms 2908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 39 ms 7032 KB Output is correct
10 Correct 28 ms 6860 KB Output is correct
11 Correct 11 ms 4216 KB Output is correct
12 Correct 13 ms 4596 KB Output is correct
13 Correct 4 ms 2908 KB Output is correct
14 Correct 46 ms 9316 KB Output is correct
15 Correct 52 ms 9128 KB Output is correct
16 Correct 9 ms 4068 KB Output is correct
17 Correct 34 ms 7632 KB Output is correct
18 Correct 19 ms 5832 KB Output is correct