oj.uz

Submission #1025338

# Submission time Handle Problem Language Result Execution time Memory
1025338 2024-07-16T21:06:16 Z nvujica Gondola (IOI14_gondola) C++14
100 / 100
 60 ms 9428 KB 
#include <bits/stdc++.h>
#include "gondola.h"

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 3e5 + 10, mod = 1e9 + 9, LOG = 30;

int a[maxn];
map <int, int> bio;
vector <pair<int, int> > v;
int pot[LOG];

int mul(int x, int y){
	return ((ll)x * y) % mod;
}

int valid(int n, int inputSeq[]){
	for(int i = 0; i < n; i++){
		a[i] = inputSeq[i] - 1;
		if(bio[a[i]]) return 0;
		bio[a[i]] = 1;
	}
	
	for(int i = 0; i < n; i++){
		if(a[i] < n){
			for(int j = 0; j < n; j++){
				if(a[(i + j) % n] < n){
					if(a[(i + j) % n] != (a[i] + j) % n) return 0;
				}
			}
			
			break;
		}
	}
	
	return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	for(int i = 0; i < n; i++){
		a[i] = gondolaSeq[i];
	}
	
	for(int i = 0; i < n; i++){
		if(a[i] > n) v.push_back({a[i], i});
	}
	
	for(int i = n - 1; i >= 0; i--){
		if(a[i] <= n || !i){
			for(int j = 0; j < n; j++){
				a[(i + j) % n] = (a[i] - 1 + j) % n + 1;
			}
			break;
		}
	}
	
//	cout << v.size() << endl;
	
	sort(v.begin(), v.end());
	
	int p = 0, l = 0;
	
	while(p < v.size()){
		replacementSeq[l] = a[v[p].se];
//		cout << a[v[p].se] << ' ';
		a[v[p].se] = n + l + 1;
		l++;
		if(a[v[p].se] == v[p].fi) p++;
	}
	
//	cout << endl;
//	cout << l;
	
	return l;
}

int calc(int x, int p){
	pot[0] = x;
	for(int i = 1; i < LOG; i++){
		pot[i] = mul(pot[i - 1], pot[i - 1]);
	}
	
	int ret = 1;
	
	for(int i = 0; i < LOG; i++){
		if(p & (1 << i)) ret = mul(ret, pot[i]);
	}
	
	return ret;
}

int countReplacement(int n, int inputSeq[]){
	if(!valid(n, inputSeq)) return 0;
	
	for(int i = 0; i < n; i++){
		a[i] = inputSeq[i];
	}
	
	for(int i = 0; i < n; i++){
		if(a[i] > n) v.push_back({a[i], i});
	}
	
//	for(int i = n - 1; i >= 0; i--){
//		if(a[i] <= n || !i){
//			for(int j = 0; j < n; j++){
//				a[(i + j) % n] = (a[i] - 1 + j) % n + 1;
//			}
//			break;
//		}
//	}
	
//	cout << v.size() << endl;

//	cout << v.size() << endl;
	
//	if(v.size() == 0) return 1;
	
	sort(v.begin(), v.end());
	
//	for(int i = 0; i < v.size(); i++){
//		cout << v[i].fi << ' ' << v[i].se << endl;
//	}
	
	int p = 0, l = n, ans = 1;
	
//	while(p < v.size()){
//		l++;
//		if(a[v[p].se] == l){
//			p++;
//			continue;
//		}
//		ans = mul(ans, v.size() - p);
//	}
	
	int zad = n;
	
	for(int i = 0; i < v.size(); i++){
//		cout << v[i].fi << ' ' << zad << ": ";
//		cout << v.size() - i << ' ' << v[i].fi - zad - 1 << endl;
		ans = mul(ans, calc(v.size() - i, v[i].fi - zad - 1));
		zad = v[i].fi;
	}
	
//	cout << endl;
//	cout << l;
	
	if(v.size() == n) ans = mul(ans, n);
	
	return ans;
}

//int main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
//	
//	int n;
//	cin >> n;
//	int inputSeq[n];
//	for(int i = 0; i < n; i++){
//		cin >> inputSeq[i];
//	}
//	cout << countReplacement(n, inputSeq);
//	
//	return 0;
//}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:67:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  while(p < v.size()){
      |        ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
gondola.cpp:151:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  151 |  if(v.size() == n) ans = mul(ans, n);
      |     ~~~~~~~~~^~~~
gondola.cpp:128:6: warning: unused variable 'p' [-Wunused-variable]
  128 |  int p = 0, l = n, ans = 1;
      |      ^
gondola.cpp:128:13: warning: unused variable 'l' [-Wunused-variable]
  128 |  int p = 0, l = n, ans = 1;
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 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 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 9 ms 4700 KB Output is correct
7 Correct 6 ms 3084 KB Output is correct
8 Correct 17 ms 6740 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct
10 Correct 22 ms 7252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 9 ms 4700 KB Output is correct
7 Correct 7 ms 3164 KB Output is correct
8 Correct 19 ms 6592 KB Output is correct
9 Correct 5 ms 3624 KB Output is correct
10 Correct 22 ms 7116 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 12 ms 4572 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 31 ms 7252 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 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 0 ms 2464 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 2392 KB Output is correct
10 Correct 1 ms 2392 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 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 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 2392 KB Output is correct
11 Correct 6 ms 3160 KB Output is correct
12 Correct 6 ms 3416 KB Output is correct
13 Correct 10 ms 3540 KB Output is correct
14 Correct 5 ms 3160 KB Output is correct
15 Correct 16 ms 4052 KB Output is correct

Subtask #7
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 0 ms 2492 KB Output is correct

Subtask #8
15.0 / 15.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 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2488 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2488 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 40 ms 7328 KB Output is correct
10 Correct 35 ms 6588 KB Output is correct
11 Correct 13 ms 4188 KB Output is correct
12 Correct 16 ms 4444 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 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2448 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 41 ms 7276 KB Output is correct
10 Correct 32 ms 6620 KB Output is correct
11 Correct 13 ms 4184 KB Output is correct
12 Correct 16 ms 4440 KB Output is correct
13 Correct 4 ms 2908 KB Output is correct
14 Correct 56 ms 8652 KB Output is correct
15 Correct 60 ms 9428 KB Output is correct
16 Correct 10 ms 3928 KB Output is correct
17 Correct 40 ms 7084 KB Output is correct
18 Correct 22 ms 5344 KB Output is correct