oj.uz

답안 #138745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138745 2019-07-30T09:33:20 Z MohamedAhmed04 곤돌라 (IOI14_gondola) C++14
60 / 100
 61 ms 4856 KB 
#include "gondola.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std ;

int valid(int n, int arr[])
{
	int st = -1;
	for(int i = 0 ; i < n ; ++i)
	{
		if(arr[i] <= n)
		{
			st = i ;
			break ;
		}
	}
	map<int , int>mp ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(mp[arr[i]] > 0)
			return 0 ;
		mp[arr[i]]++ ;
	}
	if(st == -1)
		return 1 ;
	int idx = st , cnt = 0;
	while(true)
	{
		idx++ ;
		idx %= n ;
		cnt++ ;
		if(idx == st)
			break ;
		if(arr[idx] <= n)
			continue ;
		arr[idx] = (arr[st] + cnt) % n ;
		if(arr[idx] == 0)
			arr[idx] = n ;
	}
	idx = st , cnt = 0 ;
	while(true)
	{
		idx++ ;
		idx %= n ;
		cnt++ ;
		if(idx == st)
			break ;
		int x = (arr[st] + cnt) % n ;
		if(x == 0)
			x = n ;
		if(x != arr[idx] && arr[idx] <= n)
			return 0 ;
	}
    return 1;
}

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

int replacement(int n, int arr[], int replacementSeq[])
{
	int st = -1 , MAX = *max_element(arr , arr + n);
	map<int , int>mp ;
	for(int i = 0 ; i < n ; ++i)
		mp[arr[i]] = 1 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(arr[i] <= n)
		{
			st = i ;
			break ;
		}
	}
	vector< pair<int , int> >vp ;
	if(st == -1)
	{
		for(int i = 0 ; i < n ; ++i)
			vp.push_back({arr[i] , i+1}) ;
	}
	else
	{
		int idx = st , cnt = 0;
		while(true)
		{
			idx++ ;
			idx %= n ;
			cnt++ ;
			if(idx == st)
				break ;
			if(arr[idx] <= n)
				continue ;
			int x = (arr[st] + cnt) % n ;
			if(x == 0)
				x = n ;
			vp.push_back({arr[idx] , x}) ;
		}
	}
	sort(vp.begin() , vp.end()) ;
	int ans = 0 , last = n+1;
	for(int i = 0 ; i < vp.size() ; ++i)
	{
		replacementSeq[ans] = vp[i].second ;
		ans++ ;
		for(int j = last ; j < vp[i].first ; ++j)
		{
			replacementSeq[ans] = j ;
			ans++ ;
		}
		last = vp[i].first + 1 ;
	}
	return ans ;
}

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

int countReplacement(int n, int arr[])
{
	if(!valid(n , arr))
		return 0 ;
	int a = 0 , b = 0 , cnt = 0;
	for(int i = 0 ; i < n ; ++i)
	{
		if(arr[i] > n)
			cnt++ ;
		if(arr[i] == n+2)
			a = 1 ;
		if(arr[i] == n+3)
			b = 1 ;
	}
	if(cnt == n)
	{
		if(n == 1 || n == 3)
			return 1 ;
		return 2 ;
	}
	if(a && b)
		return 2 ;
	return 1 ;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < vp.size() ; ++i)
                  ~~^~~~~~~~~~~
gondola.cpp:61:16: warning: unused variable 'MAX' [-Wunused-variable]
  int st = -1 , MAX = *max_element(arr , arr + n);
                ^~~

Subtask #1
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

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 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 21 ms 2296 KB Output is correct
7 Correct 14 ms 760 KB Output is correct
8 Correct 37 ms 4088 KB Output is correct
9 Correct 13 ms 1528 KB Output is correct
10 Correct 50 ms 4600 KB Output is correct

Subtask #3
10.0 / 10.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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 21 ms 2284 KB Output is correct
7 Correct 14 ms 760 KB Output is correct
8 Correct 37 ms 3960 KB Output is correct
9 Correct 13 ms 1528 KB Output is correct
10 Correct 50 ms 4472 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 25 ms 2168 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 61 ms 4728 KB Output is correct

Subtask #4
5.0 / 5.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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.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 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #6
20.0 / 20.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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 32 ms 4344 KB Output is correct
12 Correct 39 ms 4856 KB Output is correct
13 Correct 31 ms 2940 KB Output is correct
14 Correct 39 ms 4344 KB Output is correct
15 Correct 29 ms 3172 KB Output is correct

Subtask #7
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

Subtask #8
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 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
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 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 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 376 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -