oj.uz

답안 #926837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926837 2024-02-13T21:23:11 Z NintsiChkhaidze 곤돌라 (IOI14_gondola) C++17
75 / 100
 35 ms 6980 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
using namespace std;
int b[200005],c[200005],a[200005];
const int mod = 1e9 + 9;
 
int valid(int n, int gondolaSeq[]){
	map <int,int> mp;
	
	int k = -1;
	for (int i=0;i<n;i++){
		a[i] = gondolaSeq[i];
		if (mp.find(a[i]) != mp.end()) return 0;
		mp[a[i]] = 1;
 		if (a[i] > n) continue;
		if (k == -1) k= i;
		else if (a[k] > a[i]) k = i;
	}
	if (k==-1) return 1;
		
	int m = 0;
	int st = a[k];
	for (int j = k; j < n; j++)
		if (a[j] <= n) b[++m] = a[j],c[m] = st + (j - k);
	
	for (int j = 0; j < k; j++)
		if (a[j] <= n) b[++m] = a[j],c[m] = st + (n - k) + j;
	
	for (int i = 1; i <= m; i++){
		if (b[i] != c[i]) return 0;
	}
  	return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int k = -1;
	for (int i=0;i<n;i++){
		a[i] = gondolaSeq[i];
 		if (a[i] > n) continue;
 		
		if (k == -1) k= i;
		else if (a[k] > a[i]) k = i;
	}
	int st;
	if (k == -1) k = 0,st = 1;
	else st = a[k];
		
	for (int j = k; j < n; j++) b[j] = st + (j - k);	
	for (int j = 0; j < k; j++) b[j] = st + (n - k) + j;
	for (int j = 0; j < n; j++) if (b[j] > n)  b[j] -= n;
	
	int x = n + 1,m = -1;
	vector <pair <int,int> > vec;
	for (int i=0;i<n;i++){
		if (gondolaSeq[i] > n) vec.pb({gondolaSeq[i],i});
	}
	sort(vec.begin(),vec.end());
	
	for (int j=0;j<vec.size();j++){
		int final = vec[j].f,i = vec[j].s;
		int cur = b[i];
		while (cur != final){
			replacementSeq[++m] = cur;
			cur = x++;
		}
	}
	
	return m + 1;
}
 
//----------------------
 
ll pwr(ll a,ll b){
 	ll c=1;
 	while (b){
 		if (b&1) c=c*a%mod;
 		a=a*a%mod;
 		b/=2;
	}
 	return c;
}
 
int countReplacement(int n, int inputSeq[]){
	int chk = valid(n,inputSeq);
	if (!chk) return 0;
	
	vector <int> vec;
	vec.pb(n);
	for (int i = 0; i < n; i++)
		if(inputSeq[i] > n) vec.pb(inputSeq[i]);
	sort(vec.begin(),vec.end());
	
	ll ans = 1,len = vec.size();
	for (int i = 1; i < vec.size(); i++){
		ll dist = vec[i] - vec[i - 1] - 1;
		if (dist > 0) ans = ans * pwr(len - i,dist) % mod;
	}
	
	int k = -1;
	for (int i=0;i<n;i++){
 		if (inputSeq[i] <= n) k = i;
	}
	if (k == -1) {
		for (int i=1;i<=n;i++)	
			ans=ans*i%mod;
	}
	return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int j=0;j<vec.size();j++){
      |               ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 1; i < vec.size(); i++){
      |                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 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 2500 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 10 ms 4524 KB Output is correct
7 Correct 7 ms 652 KB Output is correct
8 Correct 20 ms 6236 KB Output is correct
9 Correct 7 ms 3676 KB Output is correct
10 Correct 24 ms 6736 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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 10 ms 4444 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 20 ms 6204 KB Output is correct
9 Correct 6 ms 3676 KB Output is correct
10 Correct 23 ms 6772 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 14 ms 4244 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 34 ms 6980 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2848 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 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 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 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 7 ms 2884 KB Output is correct
12 Correct 8 ms 2908 KB Output is correct
13 Correct 11 ms 3564 KB Output is correct
14 Correct 7 ms 2888 KB Output is correct
15 Correct 17 ms 4436 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2488 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 34 ms 6744 KB Output is correct
10 Correct 26 ms 5952 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 16 ms 4064 KB Output is correct
13 Incorrect 3 ms 608 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2400 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2428 KB Output is correct
7 Correct 1 ms 2400 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 35 ms 6656 KB Output is correct
10 Correct 29 ms 6132 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 12 ms 4172 KB Output is correct
13 Incorrect 3 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -