oj.uz

Submission #289408

# Submission time Handle Problem Language Result Execution time Memory
289408 2020-09-02T15:59:23 Z Shafin666 Gondola (IOI14_gondola) C++14
75 / 100
 54 ms 7280 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<ll, ll>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
 
const int maxn = 3e5+10;
 
int next(int p, int n) {
	int ret = (p + 1) % n;
	return (ret == 0)? n : ret;
}
 
int prev(int p, int n) {
	if(p == 0) return n-1;
	else return p-1;
}

int valid(int n, int inputSeq[])
{
	set<int> s;
	for(int i = 0; i < n; i++) s.insert(inputSeq[i]);
	if(s.size() != n) return 0;

	vector<pii> v;
	for(int i = 0; i < n; i++) {
		if(inputSeq[i] <= n) v.pb({inputSeq[i], i});
	}

	if(v.empty()) return 1;

	sort(v.begin(), v.end());
	for(int i = 0; i < v.size() - 1; i++) {
		int del = v[i+1].first - v[i].first;
		int del2 = v[i+1].second - v[i].second;
		if(del2 < 0) del2 += n;

		if(del != del2) return 0;
	}
  	return 1;
}
 
//----------------------
 
int pos[maxn];
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	memset(pos, -1, sizeof pos);
 
	vector<int> v, dummy, target(n);
	int mx = 0, none = 1;
 
	for(int i = 0; i < n; i++) {
		if(gondolaSeq[i] > n) {
			dummy.pb(i);
			pos[gondolaSeq[i]] = i;
			mx = max(mx, gondolaSeq[i]);
		}
		else none = 0;
	}

	for(int i = 0; i < n; i++) target[i] = gondolaSeq[i];
 
	if(!none) {
		for(int i = 0; i < n; i++) {
			if(gondolaSeq[prev(i, n)] >= 1 && gondolaSeq[prev(i, n)] <= n)
				gondolaSeq[i] = next(gondolaSeq[prev(i, n)], n);
		}
 
		for(int i = 0; i < n; i++) {
			if(gondolaSeq[prev(i, n)] >= 1 && gondolaSeq[prev(i, n)] <= n)
				gondolaSeq[i] = next(gondolaSeq[prev(i, n)], n);
		}
	}
	else {
		for(int i = 0; i < n; i++) gondolaSeq[i] = i+1;
	}
 
	for(int i = n+1, d = 0; i <= mx; i++) {
		if(pos[i] == -1) {
			while(gondolaSeq[dummy[d]] == target[dummy[d]]) d++;
			v.pb(gondolaSeq[dummy[d]]), gondolaSeq[dummy[d]] = i;
		}
		else v.pb(gondolaSeq[pos[i]]), gondolaSeq[pos[i]] = i;
	} 
 
	int idx = 0;
	for(auto i : v) replacementSeq[idx++] = i;
 
  	return v.size();
}
 
//----------------------
 
const ll mod = 1e9+9;

ll bigmod(ll a, ll b) {
	if(b == 0) return 1;
	ll x = bigmod(a, b/2);
	x = (x * x) % mod;
	if(b & 1) x = (x * a) % mod;
	return x;
}

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n, inputSeq)) return 0;

	vector<ll> v;
	for(ll i = 0; i < n; i++) v.pb(inputSeq[i]);

	sort(v.begin(), v.end(), greater<ll>());

	ll ret = 1;
	if(v[n-1] > n) {
		for(ll i = n; i >= 1; i--) ret = (ret * 1) % mod, v.pb(i);
		ret = (ret * 2) % mod;
	}
	

	for(ll i = 0; i < v.size() - 1; i++) {
		ll now = v[i]; 
		if(v[i] <= n+1) break;
		ll nxt = max(n * 1LL, v[i+1]);

		ll btn = now - nxt - 1;
		ret = (ret * bigmod(i+1, btn)) % mod;
	}

  	return ret;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:28:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |  if(s.size() != n) return 0;
      |     ~~~~~~~~~^~~~
gondola.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i = 0; i < v.size() - 1; i++) {
      |                 ~~^~~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:127:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(ll i = 0; i < v.size() - 1; i++) {
      |                ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 16 ms 3576 KB Output is correct
7 Correct 34 ms 4216 KB Output is correct
8 Correct 31 ms 6508 KB Output is correct
9 Correct 10 ms 2300 KB Output is correct
10 Correct 37 ms 7280 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 17 ms 3576 KB Output is correct
7 Correct 34 ms 4216 KB Output is correct
8 Correct 31 ms 6508 KB Output is correct
9 Correct 10 ms 2300 KB Output is correct
10 Correct 37 ms 7280 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 17 ms 2432 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 54 ms 6384 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 2 ms 1536 KB Output is correct
5 Correct 1 ms 1512 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Correct 2 ms 1664 KB Output is correct
9 Correct 2 ms 1536 KB Output is correct
10 Correct 2 ms 1536 KB Output is correct
11 Correct 14 ms 2560 KB Output is correct
12 Correct 16 ms 2688 KB Output is correct
13 Correct 17 ms 2808 KB Output is correct
14 Correct 15 ms 2688 KB Output is correct
15 Correct 28 ms 3676 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 47 ms 4880 KB Output is correct
10 Correct 39 ms 4472 KB Output is correct
11 Correct 13 ms 1664 KB Output is correct
12 Correct 17 ms 1920 KB Output is correct
13 Incorrect 4 ms 768 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 46 ms 4984 KB Output is correct
10 Correct 38 ms 4480 KB Output is correct
11 Correct 13 ms 1664 KB Output is correct
12 Correct 16 ms 1920 KB Output is correct
13 Incorrect 4 ms 768 KB Output isn't correct
14 Halted 0 ms 0 KB -