oj.uz

Submission #931804

# Submission time Handle Problem Language Result Execution time Memory
931804 2024-02-22T11:04:59 Z OAleksa Gondola (IOI14_gondola) C++14
55 / 100
 28 ms 6096 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

int valid(int n, int input[])
{
   vector<int> a;
   for (int i = 0;i < n;i++)
      a.push_back(input[i]);
   for (int i = 0;i < n;i++)
      a.push_back(input[i]);
   int mn = -1;
   map<int, int> cnt;
   for (int i = 0;i < n;i++) {
      cnt[a[i]]++;
      if (mn == -1 || a[i] < a[mn])
         mn = i;
   }
   for (auto u : cnt) {
      if (u.s > 1)
         return 0;
   }
   for (int i = mn, j = 0;j < n;i++,j++) {
      if (a[i] > n)
         continue;
      if (a[i] != a[mn] + j)
         return 0;
   }
   return 1;
}

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

int replacement(int n, int g[], int ans[])
{
   int sz = 0;
   if (!valid(n, g))
      return sz;
   vector<int> a;
   for (int i = 0;i < n;i++)
      a.push_back(g[i]);
   for (int i = 0;i < n;i++)
      a.push_back(g[i]);
   int mn = -1;
   for (int i = 0;i < n;i++) {
      if (a[i] <= n && (mn == -1 || a[i] < a[mn]))
         mn = i;
   }
   vector<pair<int, int>> pos;
   if (mn == -1) {
      mn = 0;
      for (int i = 0;i < n;i++) {
         if (a[i] < a[mn])
            mn = i;
      }
      for (int i = mn, j = 1;j <= n;i++, j++) {
         pos.push_back({a[i], j});
      }
   }
   else {
      for (int i = mn, j = 0;j < n;i++, j++) {
         if (a[i] > n) {
            int x = a[mn] + j;
            if (x > n)
               x -= n;
            pos.push_back({a[i], x});
         }
      }
   }
   sort(pos.begin(), pos.end());
   int lst = n;
   for (auto i : pos) {
      int br = i.s, x = i.f;
      while (x > lst) {
         ans[sz++] = br;
         br = ++lst;
      }
   }
   return sz;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2448 KB Output is correct
7 Correct 21 ms 4304 KB Output is correct
8 Correct 15 ms 4560 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 17 ms 5328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 22 ms 4296 KB Output is correct
8 Correct 16 ms 4560 KB Output is correct
9 Correct 5 ms 1752 KB Output is correct
10 Correct 17 ms 5328 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 15 ms 2516 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 28 ms 5388 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 1 ms 544 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 18 ms 5524 KB Output is correct
12 Correct 20 ms 6096 KB Output is correct
13 Correct 21 ms 3520 KB Output is correct
14 Correct 19 ms 5468 KB Output is correct
15 Correct 20 ms 3256 KB Output is correct

Subtask #7
0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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