oj.uz

Submission #915721

# Submission time Handle Problem Language Result Execution time Memory
915721 2024-01-24T15:46:06 Z ByeWorld Gondola (IOI14_gondola) C++14
55 / 100
 28 ms 7896 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+1, num = (ll)(sw.size());
	for(auto in : sw){
		ll idx = in.se, val = in.fi; // num -> val

		ANS = mul(ANS, expo(num, val-sta[idx]-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];
      |               ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:171:5: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
  171 |  ll cnt = n+1, num = (ll)(sw.size());
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 2392 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
6 Correct 11 ms 4568 KB Output is correct
7 Correct 8 ms 3800 KB Output is correct
8 Correct 23 ms 6868 KB Output is correct
9 Correct 6 ms 3676 KB Output is correct
10 Correct 24 ms 7372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2408 KB Output is correct
2 Correct 1 ms 2500 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 11 ms 4672 KB Output is correct
7 Correct 8 ms 3800 KB Output is correct
8 Correct 20 ms 6616 KB Output is correct
9 Correct 7 ms 3676 KB Output is correct
10 Correct 24 ms 7372 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 3100 KB Output is correct
14 Correct 1 ms 2488 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 2392 KB Output is correct
2 Correct 1 ms 2804 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 #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2492 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 2492 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 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 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 2648 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2488 KB Output is correct
5 Correct 1 ms 2492 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 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 23 ms 7368 KB Output is correct
12 Correct 26 ms 7896 KB Output is correct
13 Correct 23 ms 6220 KB Output is correct
14 Correct 23 ms 7368 KB Output is correct
15 Correct 28 ms 6216 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -