oj.uz

Submission #923017

# Submission time Handle Problem Language Result Execution time Memory
923017 2024-02-06T12:38:17 Z allin27x Gondola (IOI14_gondola) C++17
100 / 100
 56 ms 5968 KB 
#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"

#define int long long
const int mod = 1e9+9;


int pw(int a, int p){
	if (p==0) return 1;
	if (p&1) return (a*pw(a, p-1)) %mod;
	int r = pw(a,p/2)%mod;
	return (r*r)%mod;
}


signed valid(signed n, signed S[]){
	set<int> s; for(int i=0; i<n; i++) s.insert(S[i]); if (s.size()<n) return 0;
	int ind = -1;
	for (int i=0; i<n; i++) if (S[i] <= n) {ind = i; break;}
	if (ind == -1) return 1;
	int t = S[ind];
	for (int i=ind+1; i!=ind; i++, i%=n){
		t++; if (t==n+1) t = 1;
		if (S[i] <= n && S[i] != t) return 0;
	}
	return 1;
}



signed replacement(signed n, signed S[], signed replacementSeq[]){
	int ind = -1;
	for (int i=0; i<n; i++) if (S[i] <= n) {ind = i; break;}
	int bg = -1; map<int,int> tr; 

	if (ind == -1){
		for (int i=0; i<n; i++){
			tr[S[i]] = i+1; bg= max(bg,(int)S[i]);
		}
	} else {
		int t = S[ind];
		for (int i=(ind+1)%n; i!=ind; i++, i%=n){
			t++; if (t==n+1) t = 1;
			if (S[i] > n) {tr[S[i]] = t; bg=max(bg,(int)S[i]);}
		}
	}
	if (bg==-1) return 0;
	int bgm = tr[bg];
	tr.erase(bg);
	for (int i=n+1; i<=bg; i++){
		if (tr.count(i)){
			replacementSeq[i-(n+1)] = tr[i];
		} else {
			replacementSeq[i-(n+1)] = bgm;
			bgm = i; 
		}
	}
	return (bg-(n+1) + 1);

}

signed countReplacement(signed n, signed S[]){
	if (!valid(n,S)) return 0;
	int res = 1;
	set<int>tr; for (int i=0; i<n; i++) tr.insert(S[i]);
	int bigger = 0;
	for (int x: tr) if (x>=n+1) bigger++;
	if (!bigger) return 1;
	if (bigger == n) res *= n;
	tr.insert(n);
	auto x = tr.lower_bound(n);
	while (1){
		auto nx = tr.lower_bound((*x) + 1);
		if (nx == tr.end()) return res;
		res *= pw(bigger, (*nx) - (*x) - 1); res %= mod;
		bigger--;
		x = nx;
	}
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:18:65: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |  set<int> s; for(int i=0; i<n; i++) s.insert(S[i]); if (s.size()<n) return 0;
      |                                                         ~~~~~~~~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 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 0 ms 344 KB Output is correct
6 Correct 8 ms 2396 KB Output is correct
7 Correct 20 ms 4280 KB Output is correct
8 Correct 15 ms 4460 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 18 ms 4956 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2396 KB Output is correct
7 Correct 20 ms 4144 KB Output is correct
8 Correct 16 ms 4656 KB Output is correct
9 Correct 6 ms 1628 KB Output is correct
10 Correct 18 ms 5052 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 9 ms 2300 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 25 ms 5212 KB Output is correct

Subtask #4
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 588 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 6 ms 1112 KB Output is correct
12 Correct 7 ms 1112 KB Output is correct
13 Correct 19 ms 3272 KB Output is correct
14 Correct 6 ms 1368 KB Output is correct
15 Correct 21 ms 3420 KB Output is correct

Subtask #7
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 448 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 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 5 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 40 ms 4444 KB Output is correct
10 Correct 31 ms 3932 KB Output is correct
11 Correct 11 ms 1620 KB Output is correct
12 Correct 14 ms 1884 KB Output is correct
13 Correct 3 ms 604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 40 ms 4444 KB Output is correct
10 Correct 33 ms 3908 KB Output is correct
11 Correct 11 ms 1624 KB Output is correct
12 Correct 14 ms 1884 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 49 ms 5524 KB Output is correct
15 Correct 56 ms 5968 KB Output is correct
16 Correct 9 ms 1372 KB Output is correct
17 Correct 37 ms 4312 KB Output is correct
18 Correct 19 ms 2396 KB Output is correct