oj.uz

Submission #51667

# Submission time Handle Problem Language Result Execution time Memory
51667 2018-06-19T18:41:41 Z Mamnoon_Siam Gondola (IOI14_gondola) C++17
40 / 100
 54 ms 6484 KB 
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};


int valid(int n, int inputSeq[]) {
	if(n == 1) return 1;
	int idx = -1, id = -1;
	for(int i = 0; i < n; i++) {
		if(inputSeq[i] <= n) {
			idx = i, id = inputSeq[i];
			break;
		}
	}
	set<int> st(inputSeq, inputSeq + n);
	if(idx == -1 or st.size() != n) return int(st.size() == n);
	vector<int> v(n);
	int flag = 1;
	for(int val = id, i = idx; val != id or flag; val = val == n ? 1 : val + 1, i = (i + 1) % n) {
		v[i] = val; flag = 0;
	}
	for(int i = 0; i < n; i++) {
		if(inputSeq[i] <= n) {
			if(inputSeq[i] != v[i])
				return 0;
		}
	} return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  return -2;
}

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

const int mod = 1e9 + 9;

int qpow(int b, int p) {
	if(p < 0) return qpow(qpow(b, -p), mod - 2);
	int ret = 1; while(p) {
		if(p & 1) ret = (1LL * ret * b) % mod;
		b = (1LL * b * b) % mod, p >>= 1;
	} return ret;
}

int countReplacement(int n, int inputSeq[]) {
	if(!valid(n, inputSeq)) return 0;
	vector<int> v;
	for(int i = 0; i < n; i++) {
		if(inputSeq[i] > n)
			v.push_back(inputSeq[i]);
	}
	sort(all(v));
	int ret = 1;
	int prev = n;
	for(int i = 0; i < v.size(); i++) {
		ret = (1LL * ret * qpow(v.size() - i, v[i] - prev - 1)) % mod;
		prev = v[i];
	} return ret;
}

Compilation message

gondola.cpp: In function 'int myrand(int, int)':
gondola.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
gondola.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:42:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == -1 or st.size() != n) return int(st.size() == n);
                  ~~~~~~~~~~^~~~
gondola.cpp:42:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(idx == -1 or st.size() != n) return int(st.size() == n);
                                             ~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 464 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 12 ms 2584 KB Output is correct
7 Correct 42 ms 3864 KB Output is correct
8 Correct 26 ms 4376 KB Output is correct
9 Correct 8 ms 4376 KB Output is correct
10 Correct 31 ms 5272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5272 KB Output is correct
2 Correct 2 ms 5272 KB Output is correct
3 Correct 2 ms 5272 KB Output is correct
4 Correct 2 ms 5272 KB Output is correct
5 Correct 2 ms 5272 KB Output is correct
6 Correct 12 ms 5272 KB Output is correct
7 Correct 39 ms 5272 KB Output is correct
8 Correct 26 ms 5272 KB Output is correct
9 Correct 8 ms 5272 KB Output is correct
10 Correct 24 ms 5272 KB Output is correct
11 Correct 2 ms 5272 KB Output is correct
12 Correct 2 ms 5272 KB Output is correct
13 Correct 21 ms 5272 KB Output is correct
14 Correct 2 ms 5272 KB Output is correct
15 Correct 52 ms 5272 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5272 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5272 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5272 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5272 KB Output is correct
2 Correct 2 ms 5272 KB Output is correct
3 Correct 2 ms 5272 KB Output is correct
4 Correct 2 ms 5272 KB Output is correct
5 Correct 2 ms 5272 KB Output is correct
6 Correct 2 ms 5272 KB Output is correct
7 Correct 2 ms 5272 KB Output is correct
8 Correct 2 ms 5272 KB Output is correct
9 Correct 52 ms 5272 KB Output is correct
10 Correct 40 ms 5272 KB Output is correct
11 Correct 16 ms 5272 KB Output is correct
12 Correct 19 ms 5272 KB Output is correct
13 Incorrect 5 ms 5272 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5272 KB Output is correct
2 Correct 2 ms 5272 KB Output is correct
3 Correct 2 ms 5272 KB Output is correct
4 Correct 2 ms 5272 KB Output is correct
5 Correct 2 ms 5272 KB Output is correct
6 Correct 2 ms 5272 KB Output is correct
7 Correct 2 ms 5272 KB Output is correct
8 Correct 2 ms 5272 KB Output is correct
9 Correct 54 ms 6484 KB Output is correct
10 Correct 39 ms 6484 KB Output is correct
11 Correct 16 ms 6484 KB Output is correct
12 Correct 18 ms 6484 KB Output is correct
13 Incorrect 5 ms 6484 KB Output isn't correct
14 Halted 0 ms 0 KB -