oj.uz

Submission #50882

# Submission time Handle Problem Language Result Execution time Memory
50882 2018-06-14T04:14:19 Z mirbek01 Gondola (IOI14_gondola) C++17
100 / 100
 38 ms 12196 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;
}

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

const int mod = 1e9 + 9;

int bp(int a, int n){
      long long res = 1;
      while(n){
            if(n & 1)
                  res = (res * 1ll * a) % mod;
            a = (a * 1ll * a) % mod;
            n >>= 1;
      }
      return res;
}

int countReplacement(int n, int inputSeq[])
{
      if(!valid(n, inputSeq)) return 0;
      long long ans;
      vector <int> v;
      for(int i = 0; i < n; i ++){
            if(inputSeq[i] > n) v.push_back(inputSeq[i]);
      }
      ans = (v.size() == n)?n:1;
      sort(v.begin(), v.end());
      int l = n + 1;
      for(int i = 0; i < v.size(); i ++){
            ans = (ans * bp(v.size() - i, v[i] - l)) % mod;
            l = v[i] + 1;
      }
      return ans;
}

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 ++){
                      ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       ans = (v.size() == n)?n:1;
              ~~~~~~~~~^~~~
gondola.cpp:99:24: 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 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 2 ms 740 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Correct 14 ms 1664 KB Output is correct
7 Correct 23 ms 3024 KB Output is correct
8 Correct 18 ms 3300 KB Output is correct
9 Correct 14 ms 3300 KB Output is correct
10 Correct 28 ms 3980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3980 KB Output is correct
2 Correct 2 ms 3980 KB Output is correct
3 Correct 2 ms 3980 KB Output is correct
4 Correct 2 ms 3980 KB Output is correct
5 Correct 2 ms 3980 KB Output is correct
6 Correct 17 ms 3980 KB Output is correct
7 Correct 31 ms 4924 KB Output is correct
8 Correct 19 ms 5176 KB Output is correct
9 Correct 14 ms 5176 KB Output is correct
10 Correct 32 ms 5836 KB Output is correct
11 Correct 2 ms 5836 KB Output is correct
12 Correct 2 ms 5836 KB Output is correct
13 Correct 9 ms 5836 KB Output is correct
14 Correct 2 ms 5836 KB Output is correct
15 Correct 23 ms 6076 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6076 KB Output is correct
2 Correct 2 ms 6076 KB Output is correct
3 Correct 2 ms 6076 KB Output is correct
4 Correct 2 ms 6076 KB Output is correct
5 Correct 2 ms 6076 KB Output is correct
6 Correct 2 ms 6076 KB Output is correct
7 Correct 3 ms 6076 KB Output is correct
8 Correct 3 ms 6076 KB Output is correct
9 Correct 3 ms 6076 KB Output is correct
10 Correct 3 ms 6076 KB Output is correct
11 Correct 12 ms 6576 KB Output is correct
12 Correct 13 ms 6692 KB Output is correct
13 Correct 18 ms 7132 KB Output is correct
14 Correct 12 ms 7132 KB Output is correct
15 Correct 25 ms 8248 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8248 KB Output is correct
2 Correct 2 ms 8248 KB Output is correct
3 Correct 2 ms 8248 KB Output is correct
4 Correct 2 ms 8248 KB Output is correct
5 Correct 2 ms 8248 KB Output is correct
6 Correct 2 ms 8248 KB Output is correct
7 Correct 2 ms 8248 KB Output is correct
8 Correct 3 ms 8248 KB Output is correct
9 Correct 23 ms 8248 KB Output is correct
10 Correct 20 ms 8248 KB Output is correct
11 Correct 10 ms 8248 KB Output is correct
12 Correct 9 ms 8248 KB Output is correct
13 Correct 5 ms 8248 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8248 KB Output is correct
2 Correct 3 ms 8248 KB Output is correct
3 Correct 2 ms 8248 KB Output is correct
4 Correct 3 ms 8248 KB Output is correct
5 Correct 2 ms 8248 KB Output is correct
6 Correct 3 ms 8248 KB Output is correct
7 Correct 2 ms 8248 KB Output is correct
8 Correct 2 ms 8248 KB Output is correct
9 Correct 21 ms 8652 KB Output is correct
10 Correct 21 ms 9108 KB Output is correct
11 Correct 8 ms 9108 KB Output is correct
12 Correct 9 ms 9108 KB Output is correct
13 Correct 4 ms 9108 KB Output is correct
14 Correct 35 ms 10536 KB Output is correct
15 Correct 38 ms 11400 KB Output is correct
16 Correct 7 ms 11400 KB Output is correct
17 Correct 23 ms 11944 KB Output is correct
18 Correct 14 ms 12196 KB Output is correct