oj.uz

Submission #288002

# Submission time Handle Problem Language Result Execution time Memory
288002 2020-09-01T07:47:03 Z theStaticMind Gondola (IOI14_gondola) C++14
60 / 100
 45 ms 5368 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;

#include "gondola.h"

int valid(int n, int arr[]){
	int x = -1;

	set<int> S;
	for(int i = 0; i < n; i++) S.insert(arr[i]);
	if(sz(S) != n) return 0;

	for(int i = 0; i < n; i++){
		if(arr[i] <= n){
			x = i;
			break;
		}
	}
	if(x == -1) return 1;

	for(int i = 0; i < n; i++){
		if(arr[(x + i) % n] <= n && arr[(x + i) % n] != (arr[x] + i - 1) % n + 1) return 0;
	}
	return 1;

}

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

int replacement(int n, int arr[], int ans[]){
	vector<int> A(n);
	for(int i = 0; i < n; i++) A[i] = arr[i];

	map<int, int> S;
	for(int i = 0; i < n; i++) S[A[i]] = i;

	int x = 0;
	for(int i = 0; i < n; i++){
		if(arr[i] <= n){
			x = i;
			break;
		}
	}
	for(int i = 0; i < n; i++){
		arr[(x + i) % n] = (arr[x] + i - 1) % n + 1;
	}

	int X = max_element(all(A)) - A.begin();

	for(int i = n + 1; i <= A[X]; i++){
		if(S.count(i)) ans[i - n - 1] = arr[S[i]], arr[S[i]] = i;
		else ans[i - n - 1] = arr[X], arr[X] = i;
	}
	return A[X] - n;

}

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

int countReplacement(int n, int arr[]){
	
	if(!valid(n, arr)) return 0;

	int ans = 1;
	
	vector<int> A(n);
	for(int i = 0; i < n; i++) A[i] = arr[i];

	map<int, int> S;
	for(int i = 0; i < n; i++) if(A[i] > n) S[A[i]] = i;

	int X = max_element(all(A)) - A.begin();

	for(int i = n + 1; i <= A[X]; i++){
		if(S.count(i)){
			S.erase(i);
		}
		else{
			ans = 1ll * ans * sz(S) % modulo;
		}
	}
	return ans;

}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 13 ms 2304 KB Output is correct
7 Correct 39 ms 3832 KB Output is correct
8 Correct 30 ms 4088 KB Output is correct
9 Correct 10 ms 1664 KB Output is correct
10 Correct 34 ms 4724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 14 ms 2304 KB Output is correct
7 Correct 38 ms 3812 KB Output is correct
8 Correct 27 ms 4088 KB Output is correct
9 Correct 10 ms 1664 KB Output is correct
10 Correct 30 ms 4728 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 17 ms 2176 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 45 ms 4856 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 31 ms 4728 KB Output is correct
12 Correct 35 ms 5368 KB Output is correct
13 Correct 38 ms 2928 KB Output is correct
14 Correct 30 ms 4736 KB Output is correct
15 Correct 34 ms 2464 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 0 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 0 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -