oj.uz

Submission #642078

# Submission time Handle Problem Language Result Execution time Memory
642078 2022-09-18T12:09:29 Z QwertyPi Gondola (IOI14_gondola) C++14
100 / 100
 67 ms 6140 KB 
#include <bits/stdc++.h>
using namespace std;

#ifndef hkoi
#include "gondola.h"
#endif

typedef long long ll;

void rotate(int n, int a[], int x){
	int b[n];
	for(int i = 0; i < n; i++){
		b[i] = a[(i + n - x) % n];
	}
	for(int i = 0; i < n; i++){
		a[i] = b[i];
	}
}

bool init(int n, int a[]){
	for(int i = 0; i < n; i++){
		if(a[i] <= n){
			rotate(n, a, a[i] - (i + 1));
			break;
		}
	}
	for(int i = 0; i < n; i++){
		if(a[i] <= n && a[i] != i + 1){
			return false;
		}
	}
	set<int> S;
	for(int i = 0; i < n; i++){
		S.insert(a[i]);
	}
	if(S.size() != n){
		return false;
	}
	return true;
}

int valid(int n, int a[]){
	return init(n, a);
}

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

int replacement(int n, int a[], int r[]){
	init(n, a);
	int l = 0;
	vector<int> seq;
	for(int i = 0; i < n; i++){
		seq.push_back(i + 1);
	}
	map<int, int> A; set<int> S;
	for(int i = 0; i < n; i++)
		A[a[i]] = i;
	for(int i = 0; i < n; i++){
		if(a[i] != i + 1){
			S.insert(i);
		}
	}
	int MAX_A = *max_element(a, a + n);
	for(int i = n + 1; i <= MAX_A; i++){
		if(!A.count(i)){
			r[l++] = seq[*S.begin()];
			seq[*S.begin()] = i;
		}else{
			r[l++] = seq[A[i]];
			seq[A[i]] = i;
			S.erase(A[i]);
		}
	}
	return l;
}

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

const ll MOD = 1e9 + 9;

ll bp(ll a, ll b){
	if(b == 0) return 1;
	return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}

ll mi(ll a){
	return bp(a, MOD - 2);
}

ll C(ll n, ll r){
	ll ret = 1;
	for(ll i = n; i >= n - r + 1; i++){
		ret = (ret * i) % MOD;
	}
	for(ll i = 1; i <= r; i++){
		ret = (ret * mi(i)) % MOD;
	}
}

int countReplacement(int n, int a[]){
	bool ok = init(n, a);
	if(!ok) return 0;
	set<int> A; for(int i = 0; i < n; i++) A.insert(a[i]);
	int MAX_A = *--A.end(), MIN_A = *A.begin();
	ll FIXED = 0, _prev = n, ans = MIN_A > n ? n : 1;
	for(auto a : A){
		if(a > n){
			ans = ans * bp(n - FIXED, a - _prev - 1) % MOD;
			_prev = a;
		}
		FIXED++;
	}
	return ans;
}

#ifdef hkoi

int a[250001];
int b[250001];
int main() {
	int ST;
	cin >> ST;
	int n; cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	if(1 <= ST && ST <= 3){
		int ans = valid(n, a);
		cout << ans << '\n';
	}else if(4 <= ST && ST <= 6){
		int l = replacement(n, a, b);
		cout << l << '\n';
		for(int i = 0; i < l; i++){
			cout << b[i] << '\n';
		}
	}else if(7 <= ST && ST <= 10){
		int ans = countReplacement(n, a);
		cout << ans << '\n';
	}
}

#endif

Compilation message

gondola.cpp: In function 'bool init(int, int*)':
gondola.cpp:36:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  if(S.size() != n){
      |     ~~~~~~~~~^~~~
gondola.cpp: In function 'll C(ll, ll)':
gondola.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
   98 | }
      | ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:104:6: warning: unused variable 'MAX_A' [-Wunused-variable]
  104 |  int MAX_A = *--A.end(), MIN_A = *A.begin();
      |      ^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 10 ms 2488 KB Output is correct
7 Correct 8 ms 1440 KB Output is correct
8 Correct 20 ms 4600 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 23 ms 5272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 10 ms 2476 KB Output is correct
7 Correct 8 ms 1492 KB Output is correct
8 Correct 20 ms 4556 KB Output is correct
9 Correct 6 ms 1620 KB Output is correct
10 Correct 24 ms 5312 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 8 ms 1492 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 41 ms 5560 KB Output is correct
12 Correct 40 ms 6140 KB Output is correct
13 Correct 45 ms 4564 KB Output is correct
14 Correct 34 ms 5480 KB Output is correct
15 Correct 38 ms 3984 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 45 ms 4784 KB Output is correct
10 Correct 36 ms 4024 KB Output is correct
11 Correct 15 ms 1600 KB Output is correct
12 Correct 15 ms 1980 KB Output is correct
13 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 240 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 44 ms 4704 KB Output is correct
10 Correct 36 ms 4008 KB Output is correct
11 Correct 13 ms 1620 KB Output is correct
12 Correct 16 ms 1952 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 53 ms 5368 KB Output is correct
15 Correct 67 ms 6104 KB Output is correct
16 Correct 9 ms 1368 KB Output is correct
17 Correct 38 ms 4076 KB Output is correct
18 Correct 20 ms 2464 KB Output is correct