oj.uz

Submission #819940

# Submission time Handle Problem Language Result Execution time Memory
819940 2023-08-10T16:03:33 Z Cyber_Wolf Gondola (IOI14_gondola) C++17
30 / 100
 7 ms 1132 KB 
#include <bits/stdc++.h>
#include "gondola.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg MOD = 1e9+9;

int valid(int n, int v[])
{
	int idx = 0;
	for(int i = 0; i < n; i++)
	{
		if(v[i] == 1)	idx = i;
	}
	int x = n, b = 1, val = 1;
	while(x--)
	{
		b &= (v[idx] == val);
		idx = (idx+1)%n;
		val++;
	}
	return b;
}


int replacement(int n, int v[], int r[])
{
	int o = 0;
	multiset<lg> mst, not_taken;
	for(int i = 0; i < n; i++)	
	{
		mst.insert(v[i]);
	}
	for(int i = 1; i <= *(--mst.end()); i++)
	{
		if(mst.find(i) == mst.end())	not_taken.insert(i);
	}
	while(not_taken.size())
	{
		int val = *(--mst.end());
		mst.erase(--mst.end());
		mst.insert(*(--not_taken.end()));
		r[o++] = *(--not_taken.end());
		not_taken.erase(--not_taken.end());
	}
	reverse(r, r+o);
	return o;
}

lg fast_power(lg n, lg k)
{
	lg ans = 1;
	while(k)
	{
		if(k&1)	ans = (ans*n)%MOD;
		n = (n*n)%MOD;
		k >>= 1;
	}
	return ans;
}

int countReplacement(int n, int in[])
{
	int mxm = 0, un = 0;
	set<lg> se;
	for(int i = 0; i < n; i++)
	{
		mxm = max(mxm, in[i]);
		un += (in[i] > n);
		se.insert(in[i]);
	}
	if(se.size() < n)	return 0;
	int ans = 1;
	for(int i = 1; i <= mxm-n-un; i++)	ans = (ans*i)%MOD;
	for(int i = 1; i < mxm-n; i++)	ans = (ans*i)%MOD;
	for(int i = 1; i < un; i++)	ans = (ans*fast_power(i, MOD-2))%MOD;
	return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:48:7: warning: unused variable 'val' [-Wunused-variable]
   48 |   int val = *(--mst.end());
      |       ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:80:15: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |  if(se.size() < n) return 0;
      |     ~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 7 ms 1132 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 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 212 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 6 ms 924 KB Output is correct
9 Correct 2 ms 448 KB Output is correct
10 Correct 6 ms 1108 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 0 ms 308 KB Output is correct
15 Correct 7 ms 1108 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 288 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 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory 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 308 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory 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 0 ms 212 KB Output is correct
5 Incorrect 1 ms 300 KB Integer -580588928 violates the range [0, 1000000008]
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Integer -580588928 violates the range [0, 1000000008]
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 0 ms 212 KB Integer -580588928 violates the range [0, 1000000008]
6 Halted 0 ms 0 KB -