oj.uz

답안 #799042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799042 2023-07-31T08:55:21 Z FatihSolak 곤돌라 (IOI14_gondola) C++17
75 / 100
 39 ms 5324 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> get(int n,int inputSeq[]){
	int pos = 0;
	for(int i = 0;i<n;i++){
		if(inputSeq[i] <= n){
			pos = (i + 1 - inputSeq[i] + n)%n;
		}
	}
	vector<int> ret;
	for(int i = pos;i < n;i++){
		ret.push_back(inputSeq[i]);
	}
	for(int i = 0;i<pos;i++){
		ret.push_back(inputSeq[i]);
	}
	return ret;
}
int valid(int n, int inputSeq[]){
	vector<int> inp = get(n,inputSeq);
	set<int> s;
	for(int i = 0;i<n;i++){
		s.insert(inp[i]);
		if(inp[i] <= n && inp[i] != i + 1){
			return 0;
		}
	}
	if(s.size() != n)	
		return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	vector<int> inp = get(n,gondolaSeq);
	map<int,int> mp;
	int maxi = 0;
	for(int i = 0;i<n;i++){
		if(inp[i] > n){
			mp[inp[i]] = i;
			if(inp[maxi] < inp[i])
				maxi = i;
		}
	}
	int l = 0;
	int tmp = inp[maxi];
	inp[maxi] = maxi + 1;
	for(int i = n + 1;i <= tmp;i++){
		if(mp.count(i) && mp[i] != maxi){
			replacementSeq[l++] = mp[i] + 1;
		}
		else{
			replacementSeq[l++] = inp[maxi];
			inp[maxi] = i;
		}
	}
	return l;
}

//----------------------
const int mod = 1e9 + 9;
int countReplacement(int n, int inputSeq[]){
	if(!valid(n,inputSeq)){
		return 0;
	}
	vector<int> inp = get(n,inputSeq);
	int ans = 1;
	bool ok = 1;
	set<int> s;
	for(int i = 0;i<n;i++){
		if(inp[i] <= n){
			ok = 0;
		}
		else s.insert(inp[i]);
	}
	if(ok){
		for(int i = 1;i<=n;i++){
			ans = (long long)ans * i % mod;
		}
	}
	if(s.size()){
		int cnt = s.size();
		for(int i = n + 1;i<=*s.rbegin();i++){
			if(s.count(i)){
				cnt--;
				continue;
			}
			ans = (long long)ans * cnt % mod;
		}
	}
	return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:29:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  if(s.size() != n)
      |     ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 304 KB Output is correct
6 Correct 8 ms 2576 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 17 ms 4532 KB Output is correct
9 Correct 6 ms 1580 KB Output is correct
10 Correct 20 ms 5324 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 2528 KB Output is correct
7 Correct 8 ms 1768 KB Output is correct
8 Correct 16 ms 4556 KB Output is correct
9 Correct 7 ms 1716 KB Output is correct
10 Correct 19 ms 5316 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 7 ms 1744 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 312 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 296 KB Output is correct
7 Correct 1 ms 212 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 424 KB Output is correct
11 Correct 8 ms 1608 KB Output is correct
12 Correct 8 ms 1736 KB Output is correct
13 Correct 21 ms 2740 KB Output is correct
14 Correct 7 ms 1704 KB Output is correct
15 Correct 22 ms 2960 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 304 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 256 KB Output is correct

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 38 ms 4692 KB Output is correct
10 Correct 28 ms 3920 KB Output is correct
11 Correct 13 ms 1744 KB Output is correct
12 Correct 15 ms 1940 KB Output is correct
13 Incorrect 5 ms 616 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 39 ms 4792 KB Output is correct
10 Correct 29 ms 4048 KB Output is correct
11 Correct 13 ms 1660 KB Output is correct
12 Correct 15 ms 1988 KB Output is correct
13 Incorrect 5 ms 596 KB Output isn't correct
14 Halted 0 ms 0 KB -