oj.uz

답안 #138784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138784 2019-07-30T10:20:43 Z Mahmoud_Adel 곤돌라 (IOI14_gondola) C++14
70 / 100
 93 ms 9076 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5, mod = 1e9+9;
int mep[N];
map<ll, ll> mark;
ll power(ll a, ll b)
{
	if(!b) return 1;
	ll temp = power(a, b/2);
	temp = (temp*temp)%mod;
	if(b%2) temp *= a, temp %= mod;
	return temp;
}
int valid(int n, int inputSeq[])
{
	for(int i=0; i<n; i++)
	{
		if(mark[inputSeq[i]]) return 0;
		else mark[inputSeq[i]] = 1;
	}
	int j = -1;
	for(int i=0; i<n; i++) if(inputSeq[i] > 0 && inputSeq[i] <= n) j = i;
	if(j == -1) return 1;
	for(int i=0; i<n; i++)
	{
		int id = (i+j)%n, jd = (i+j+1)%n;
		if(inputSeq[jd] > n) inputSeq[jd] = inputSeq[id]%n + 1;
		if(inputSeq[jd] != inputSeq[id]%n + 1) return 0;
	}
	return 1;
}

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

int replacement(int n, int inputSeq[], int replacementSeq[])
{
	memset(mep, 0, sizeof mep);
	int j = -1, c = n;
	for(int i=0; i<n; i++) if(inputSeq[i] <= n) j  = i;
	if(j == -1)
	{
		for(int i=0; i<n; i++)
		{
			int id = (i+j) % n, jd = (i+j+1) % n;
			c = max(c, inputSeq[jd]), mep[inputSeq[jd]] = i+1;
		}
		int last = -1;
		for(int i=n+1; i<c; i++)
		{
			if(mep[i]) replacementSeq[i-n-1] = mep[i];
			else replacementSeq[i-n-1] = mep[c], last = i;
		}
		if(last != -1) replacementSeq[c-n-1] = last;
		else replacementSeq[c-n-1] = mep[c];
		return c-n;	
	}
	for(int i=0; i<n; i++)
	{
		int id = (i+j) % n, jd = (i+j+1) % n;
		if(inputSeq[jd] > n) c = max(c, inputSeq[jd]), 
		mep[inputSeq[jd]] = inputSeq[id]%n + 1, inputSeq[jd] = inputSeq[id]%n + 1;
	}
	int last = -1;
	for(int i=n+1; i<c; i++)
	{
		if(mep[i]) replacementSeq[i-n-1] = mep[i];
		else replacementSeq[i-n-1] = mep[c], last = i;
	}
	if(last != -1) replacementSeq[c-n-1] = last;
	else replacementSeq[c-n-1] = mep[c];
	return c-n;
}

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

int countReplacement(int n, int inputSeq[])
{
	int tmp[n];
	for(int i=0; i<n; i++) tmp[i] = inputSeq[i];
	if(!valid(n, inputSeq)) return 0;
	for(int i=0; i<n; i++) inputSeq[i] = tmp[i];
	ll j = -1, c = n;
	vector<ll> vec;
	for(int i=0; i<n; i++) if(inputSeq[i] <= n) j  = i;
	else vec.push_back(inputSeq[i]);
	ll ans = 1;
	vec.push_back(n);
	sort(vec.begin(), vec.end());
	for(int i=0; i<vec.size()-1; i++)
	{
		ll tmp = power((ll)vec.size()-i-1, vec[i+1]-vec[i]-1);
		ans = (ans%mod * tmp%mod)%mod;
	}
	return (ans*(j==-1? n:1))%mod;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:46:8: warning: unused variable 'id' [-Wunused-variable]
    int id = (i+j) % n, jd = (i+j+1) % n;
        ^~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vec.size()-1; i++)
               ~^~~~~~~~~~~~~
gondola.cpp:84:13: warning: unused variable 'c' [-Wunused-variable]
  ll j = -1, c = n;
             ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 25 ms 3064 KB Output is correct
7 Correct 14 ms 1144 KB Output is correct
8 Correct 49 ms 5496 KB Output is correct
9 Correct 15 ms 1912 KB Output is correct
10 Correct 60 ms 6276 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 25 ms 3120 KB Output is correct
7 Correct 14 ms 1144 KB Output is correct
8 Correct 49 ms 5424 KB Output is correct
9 Correct 15 ms 1912 KB Output is correct
10 Correct 58 ms 6264 KB Output is correct
11 Correct 2 ms 396 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 25 ms 2936 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 65 ms 6544 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4188 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 5 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4188 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Incorrect 6 ms 4216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 6 ms 4216 KB Output is correct
6 Incorrect 6 ms 4216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 65 ms 6652 KB Output is correct
10 Correct 50 ms 5752 KB Output is correct
11 Correct 19 ms 2424 KB Output is correct
12 Correct 23 ms 2804 KB Output is correct
13 Correct 6 ms 888 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 63 ms 6648 KB Output is correct
10 Correct 50 ms 5624 KB Output is correct
11 Correct 19 ms 2424 KB Output is correct
12 Correct 22 ms 2804 KB Output is correct
13 Correct 6 ms 1020 KB Output is correct
14 Correct 79 ms 8052 KB Output is correct
15 Correct 93 ms 9076 KB Output is correct
16 Correct 17 ms 2168 KB Output is correct
17 Correct 60 ms 6172 KB Output is correct
18 Correct 31 ms 3828 KB Output is correct