oj.uz

Submission #754995

# Submission time Handle Problem Language Result Execution time Memory
754995 2023-06-09T08:51:20 Z AngusRitossa Gondola (IOI14_gondola) C++14
100 / 100
 43 ms 6812 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000009 
int occurance[100010];
int exists[300010];
unordered_set<int> existsSET;
int valid(int n, int inputSeq[])
{
	existsSET.clear();
	for (int i = 0; i < n; i++)
	{
		if (inputSeq[i] <= n) 
		{ 
			if (existsSET.find(inputSeq[i]) != existsSET.end()) return 0;
			occurance[inputSeq[i]] = i;
			existsSET.insert(inputSeq[i]);
		}
		else if (existsSET.find(inputSeq[i]) != existsSET.end()) return 0;
		else
		{
			existsSET.insert(inputSeq[i]);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (existsSET.find(i) != existsSET.end())
		{
			int loc = occurance[i];
			for (int j = 1; j <= n; j++)
			{
				if (existsSET.find(j) != existsSET.end())
				{
					int diff = occurance[j] + n - loc;
					diff %= n;
					int diff2 = j-i;
					if (diff != diff2) return 0;
				}
			}
			return 1;
		}
	}

	return 1;
	
}

//----------------------
int hasToDestroy[300010];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	fill_n(exists, 300010, 0);
	pair<int, int> mx = { 0, 0 };
	int ans = 0;
	int firstloc = 1;
	for (int i = 0; i < n; i++)
	{
		exists[gondolaSeq[i]] = 1;
		occurance[gondolaSeq[i]] = i;
		mx = max(mx, { gondolaSeq[i], i } );
	}	
	for (int i = 1; i <= n; i++)
	{
		if (exists[i])
		{
			firstloc = occurance[i]+1-i;
			firstloc += n;
			firstloc %= n;
			break;
		}
	}
	for (int i = 0; i < n; i++)
	{
		int initiallyhere = (i-firstloc+n)%n;
		initiallyhere++;
		if (gondolaSeq[i] != initiallyhere) hasToDestroy[gondolaSeq[i]] = initiallyhere;
	}
	int initialmx = (mx.second - firstloc +n)%n;
	initialmx++;
	exists[mx.first] = false;
	queue<int> q;
	q.push(initialmx);
	for (int i = n+1; i < mx.first; i++)
	{
		if (!exists[i]) q.push(i);
	}
	for (int i = n+1; i <= mx.first; i++)
	{
		if (!exists[i])
		{
			replacementSeq[ans++] = q.front();
			q.pop();
		}
		else
		{
			replacementSeq[ans++] = hasToDestroy[i];
		}
	}
	return ans;
}
ll pow(ll n, ll k)
{
	if (k == 0) return 1;
	ll ans = pow(n, k/2);
	ans *= ans;
	ans %= mod;
	if (k % 2) ans *= n;
	return ans % mod;
}
//----------------------

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n, inputSeq)) return 0;
	ll ans = 1;
	vector<int> v;
	ll pre = n;
	for (int i = 0; i < n; i++)
	{
		if (inputSeq[i] > n) v.push_back(inputSeq[i]);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for (ll i = v.size()-1; i >= 0; i--)
	{
		ll at = v[i];
		ll dist = at-pre-1;
		//printf("%lld %lld\n", at, dist);
		if (dist)
		{
			ll mult = pow((i+1),dist);
			//printf("%lld %lld %lld\n", at, dist, mult);
			mult %= mod;
			ans *= mult;
			ans %= mod; 
		}
		pre = at;
	}
	if (v.size() == n) ans *= n;
	ans %= mod;
	return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:140:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |  if (v.size() == n) ans *= n;
      |      ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 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 7 ms 2352 KB Output is correct
7 Correct 11 ms 1456 KB Output is correct
8 Correct 13 ms 4120 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 15 ms 4680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 2344 KB Output is correct
7 Correct 16 ms 1396 KB Output is correct
8 Correct 13 ms 4180 KB Output is correct
9 Correct 5 ms 1716 KB Output is correct
10 Correct 18 ms 4740 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 9 ms 2216 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 26 ms 6128 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1476 KB Output is correct
2 Correct 1 ms 1468 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1472 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1472 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1472 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 13 ms 2644 KB Output is correct
13 Correct 13 ms 3340 KB Output is correct
14 Correct 9 ms 2556 KB Output is correct
15 Correct 19 ms 4196 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 22 ms 4812 KB Output is correct
10 Correct 19 ms 4196 KB Output is correct
11 Correct 9 ms 1804 KB Output is correct
12 Correct 10 ms 2096 KB Output is correct
13 Correct 3 ms 724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 25 ms 4780 KB Output is correct
10 Correct 17 ms 4188 KB Output is correct
11 Correct 9 ms 1836 KB Output is correct
12 Correct 9 ms 2096 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 37 ms 5520 KB Output is correct
15 Correct 43 ms 6812 KB Output is correct
16 Correct 7 ms 1364 KB Output is correct
17 Correct 25 ms 4236 KB Output is correct
18 Correct 12 ms 2664 KB Output is correct