oj.uz

Submission #30341

# Submission time Handle Problem Language Result Execution time Memory
30341 2017-07-23T09:09:26 Z kavun Gondola (IOI14_gondola) C++14
65 / 100
 166 ms 7876 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 9;
int power(int x, int k) {
  int res = 1;
  while(k) {
    if(k & 1)
      res = (ll) res * x % mod;
    x = (ll) x * x % mod;
    k >>= 1;
  }
  return res;
}

int valid(int n, int inputSeq[])
{
  int index = -1, val = -1;
  for(int i = 0; i < n; i++)
    if(inputSeq[i] <= n)
      {
	index = i;
	val = inputSeq[i];
	break;
      }
  for(int i = index + 1; i < n; i++)
    if(inputSeq[i] <= n && (val + i - index - 1) % n + 1 != inputSeq[i])
      return 0;

  set<int> s;
  for(int i = 0; i < n; i++)
    s.insert(inputSeq[i]);
  if(s.size() == n)
    return 1;
  else 
    return 0;
}

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

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

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

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq))
    return 0;
  int ans = 1;
  set<int> rep;
  for(int i = 0; i < n; i++)
    if(inputSeq[i] > n)
      rep.insert(inputSeq[i]);
  int before = n, cnt = 0;
  for(set<int>::iterator it = rep.begin(); it != rep.end(); it++)
    {
      int x = *it;
      ans = (ll) ans * power(rep.size() - cnt, x - before - 1) % mod;
      before = x;
      cnt++;
    }
  sort(inputSeq, inputSeq+n);
  if(inputSeq[0] > n)
    ans = (ll)ans * n % mod;
  return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.size() == n)
               ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3388 KB Output is correct
2 Correct 0 ms 3388 KB Output is correct
3 Correct 0 ms 3388 KB Output is correct
4 Correct 0 ms 3388 KB Output is correct
5 Correct 0 ms 3388 KB Output is correct
6 Correct 9 ms 5104 KB Output is correct
7 Correct 9 ms 3388 KB Output is correct
8 Correct 26 ms 6688 KB Output is correct
9 Correct 9 ms 4444 KB Output is correct
10 Correct 33 ms 7348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3388 KB Output is correct
2 Correct 0 ms 3388 KB Output is correct
3 Correct 0 ms 3388 KB Output is correct
4 Correct 0 ms 3388 KB Output is correct
5 Correct 0 ms 3388 KB Output is correct
6 Correct 13 ms 5104 KB Output is correct
7 Correct 9 ms 3388 KB Output is correct
8 Correct 19 ms 6688 KB Output is correct
9 Correct 6 ms 4444 KB Output is correct
10 Correct 29 ms 7348 KB Output is correct
11 Correct 0 ms 3388 KB Output is correct
12 Correct 0 ms 3388 KB Output is correct
13 Correct 9 ms 3388 KB Output is correct
14 Correct 0 ms 3388 KB Output is correct
15 Correct 9 ms 3388 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3388 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 0 ms 3388 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 0 ms 3388 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 0 ms 3388 KB Output is correct
2 Correct 0 ms 3388 KB Output is correct
3 Correct 0 ms 3388 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3388 KB Output is correct
2 Correct 0 ms 3388 KB Output is correct
3 Correct 0 ms 3388 KB Output is correct
4 Correct 0 ms 3388 KB Output is correct
5 Correct 0 ms 3388 KB Output is correct
6 Correct 0 ms 3388 KB Output is correct
7 Correct 0 ms 3388 KB Output is correct
8 Correct 0 ms 3388 KB Output is correct
9 Correct 86 ms 6820 KB Output is correct
10 Correct 76 ms 6292 KB Output is correct
11 Correct 23 ms 4444 KB Output is correct
12 Correct 23 ms 4708 KB Output is correct
13 Correct 3 ms 3652 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3388 KB Output is correct
2 Correct 0 ms 3388 KB Output is correct
3 Correct 0 ms 3388 KB Output is correct
4 Correct 0 ms 3388 KB Output is correct
5 Correct 0 ms 3388 KB Output is correct
6 Correct 0 ms 3388 KB Output is correct
7 Correct 0 ms 3388 KB Output is correct
8 Correct 0 ms 3388 KB Output is correct
9 Correct 96 ms 6820 KB Output is correct
10 Correct 69 ms 6292 KB Output is correct
11 Correct 23 ms 4444 KB Output is correct
12 Correct 26 ms 4708 KB Output is correct
13 Correct 6 ms 3652 KB Output is correct
14 Correct 166 ms 7348 KB Output is correct
15 Correct 156 ms 7876 KB Output is correct
16 Correct 16 ms 4180 KB Output is correct
17 Correct 86 ms 6424 KB Output is correct
18 Correct 43 ms 5104 KB Output is correct