oj.uz

Submission #50551

# Submission time Handle Problem Language Result Execution time Memory
50551 2018-06-11T12:14:57 Z mirbek01 Gondola (IOI14_gondola) C++17
55 / 100
 36 ms 4908 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 2;

int valid(int n, int inputSeq[])
{
      vector <pair <int, int> > v;
      for(int i = 0; i < n; i ++)
            if(inputSeq[i] <= n)
                  v.push_back({inputSeq[i], i + 1});
      sort(v.begin(), v.end());
      for(int i = 1; i < v.size(); i ++){
            int ab = v[i].first - v[i - 1].first, ds;
            if(v[i].second > v[i - 1].second){
                  ds = v[i].second - v[i - 1].second;
            } else {
                  ds = v[i].second + (n - v[i - 1].second);
            }
            if(ds != ab) return 0;
      }
      sort(inputSeq, inputSeq + n);
      for(int i = 1; i < n; i ++){
            if(inputSeq[i] == inputSeq[i - 1]) return 0;
      }
      return 1;
}

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

int used[N];

int replacement(int n, int gondolaSeq[], int rp[])
{
      int pos = 1, mx = 0, sz = 0, id = 0;
      vector <int> v, nm(n);
      vector < pair <int, int> > d;
      for(int i = 0; i < n; i ++){
            mx = max(mx, gondolaSeq[i]);
            used[gondolaSeq[i]] = 1;
            if(gondolaSeq[i] > n){
                  d.push_back({gondolaSeq[i], i});
            }
            else
                  pos = gondolaSeq[i], id = i;
      }
      for(int i = n + 1; i <= mx; i ++){
            if(!used[i])
                  v.push_back(i);
      }
      for(int i = 0; i < n; i ++){
            nm[id] = pos;
            pos ++;
            id ++;
            if(pos > n) pos = 1;
            if(id >= n) id = 0;
      }
      sort(d.begin(), d.end());
      int cur = n + 1;
      for(int i = 0; i < d.size(); i ++){
            int ps = nm[d[i].second];
            rp[sz ++] = ps;
            while(cur < d[i].first){
                  if(!used[cur])
                        rp[sz ++] = cur;
                  cur ++;
            }
      }
      return sz;
}

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

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

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:14:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 1; i < v.size(); i ++){
                      ~~^~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < d.size(); i ++){
                      ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 16 ms 1336 KB Output is correct
7 Correct 24 ms 1972 KB Output is correct
8 Correct 18 ms 1972 KB Output is correct
9 Correct 9 ms 1972 KB Output is correct
10 Correct 30 ms 2024 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2024 KB Output is correct
2 Correct 2 ms 2024 KB Output is correct
3 Correct 2 ms 2024 KB Output is correct
4 Correct 2 ms 2024 KB Output is correct
5 Correct 2 ms 2024 KB Output is correct
6 Correct 15 ms 2024 KB Output is correct
7 Correct 26 ms 2036 KB Output is correct
8 Correct 23 ms 2036 KB Output is correct
9 Correct 12 ms 2036 KB Output is correct
10 Correct 36 ms 2036 KB Output is correct
11 Correct 2 ms 2036 KB Output is correct
12 Correct 2 ms 2036 KB Output is correct
13 Correct 8 ms 2036 KB Output is correct
14 Correct 3 ms 2036 KB Output is correct
15 Correct 23 ms 2036 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2036 KB Output is correct
2 Correct 2 ms 2036 KB Output is correct
3 Correct 2 ms 2036 KB Output is correct
4 Correct 2 ms 2036 KB Output is correct
5 Correct 2 ms 2036 KB Output is correct
6 Correct 2 ms 2036 KB Output is correct
7 Correct 3 ms 2036 KB Output is correct
8 Correct 2 ms 2036 KB Output is correct
9 Correct 2 ms 2036 KB Output is correct
10 Correct 3 ms 2036 KB Output is correct
11 Correct 16 ms 2036 KB Output is correct
12 Correct 15 ms 2704 KB Output is correct
13 Correct 28 ms 3344 KB Output is correct
14 Correct 13 ms 3344 KB Output is correct
15 Correct 24 ms 4908 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4908 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 2 ms 4908 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 2 ms 4908 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 2 ms 4908 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -