oj.uz

Submission #953695

# Submission time Handle Problem Language Result Execution time Memory
953695 2024-03-26T13:33:29 Z emad234 Gondola (IOI14_gondola) C++17
55 / 100
 33 ms 6964 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 9;
const ll mxN = 3e5 + 5;
using namespace std;
int realS[mxN];
bool allB;
bool cnt;
int aval;
int mx = 0;
int valid(int n, int inputSeq[])
{
  allB = 1;
  memset(realS, 0, sizeof(realS));
  map<int,bool>vis;
  int st = 0;
  int val = 1;
  for (int i = 0; i < n; i++)
  {
    mx = max(mx, inputSeq[i]);

    if (vis[inputSeq[i]])
      return 0;
    vis[inputSeq[i]] = 1;
    if (inputSeq[i] <= n)
    {
      allB = 0;
      aval--;
      st = i;
      val = inputSeq[i];
    }
  }
  int og = st;
  while (1)
  {
    st++;
    val++;
    if (st >= n)
      st = 0;
    if (val > n)
      val = 1;
    if(!cnt) realS[inputSeq[st]] = val;
    if (st == og)
      break;
    if (inputSeq[st] != val && inputSeq[st] <= n)
      return 0;
  }
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  if(!valid(n, gondolaSeq)) return 0;
  int id = 0;
  for (int i = n + 1; i <= mx; i++)
  {
    if (!realS[i])
    {
      replacementSeq[id] = realS[mx];
      realS[mx] = i;
    }
    else
      replacementSeq[id] = realS[i];
    id++;
  }
  return id;
}

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

int countReplacement(int n, int inputSeq[])
{
  cnt = 1;
  aval = n;
  ll ans = 1;
  if(!valid(n, inputSeq))return 0;
  int id = 0;
  for (int i = n + 1; i <= mx; i++)
  {
    if (!realS[i])
      ans *= aval;
    else
      aval--;
    ans %= mod;
  }
  if (allB)
    ans *= n;
  ans %= mod;
  return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:83:7: warning: unused variable 'id' [-Wunused-variable]
   83 |   int id = 0;
      |       ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 10 ms 4444 KB Output is correct
7 Correct 7 ms 2908 KB Output is correct
8 Correct 20 ms 6064 KB Output is correct
9 Correct 8 ms 3672 KB Output is correct
10 Correct 24 ms 6748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 10 ms 4508 KB Output is correct
7 Correct 7 ms 2908 KB Output is correct
8 Correct 20 ms 6140 KB Output is correct
9 Correct 7 ms 3676 KB Output is correct
10 Correct 24 ms 6688 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 14 ms 4188 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 33 ms 6964 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2852 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2460 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 22 ms 6500 KB Output is correct
12 Correct 26 ms 6916 KB Output is correct
13 Correct 19 ms 4696 KB Output is correct
14 Correct 26 ms 6484 KB Output is correct
15 Correct 19 ms 4432 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -