oj.uz

Submission #138695

# Submission time Handle Problem Language Result Execution time Memory
138695 2019-07-30T08:42:29 Z Bohoty Gondola (IOI14_gondola) C++14
55 / 100
 117 ms 16648 KB 
#include<bits/stdc++.h>
#include "gondola.h"

//#include "grader.cpp"
using namespace std;
const int N = 100 + 5, mod = 1e9 + 7;
int a, b, c, m;
int dp[N][N][N];
long long solve(int x, int y, int z, bool start){
  if (x > a || y > b || z > c)
    return 0;
  if (x == a && y == b && z == c)
    return 1;
  if (~dp[x][y][z])
    return dp[x][y][z];
  int n_x, n_y, n_z;
  if (start)
    n_x = n_y = n_z;
  else
    n_x = n_y = n_z = max(max(x, y), z);
  return dp[x][y][z] = (solve(x + 1, y, z, 0)
  +  solve(x, y + 1, z, 0)
  + solve(x, y, z + 1, 0)) % mod;
}
int valid(int n, int inputSeq[]){
  int mn = 1e9;
  int idx = -1;
  map < int, int > mp;
  for(int i = 0 ; i < n ; i++){
    mp[inputSeq[i]]++;
    if (inputSeq[i] < mn){
      mn = inputSeq[i], idx = i;
    }
  }
  for(auto it :mp){
    if (it.second > 1)
    return 0;
  }
  int intended = mn;
  if (intended > n)
    return 1;
  for(int i = 0 ; i < n ; i++){
    int cur = inputSeq[(i + idx) % n];
    if (cur != intended){
      if (cur <= n)
        return 0;
    }
    intended++;
    if (intended > n)
    intended -= n;
  }
  return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
  int mn = 1e9;
  int idx = -1;
  set < int > st, elements;
  int f[250001], now[250001];
  memset(f,0,sizeof f);
  memset(now,0,sizeof now);
  for(int i = 0 ; i < 250001 ; i++)
    now[i] = i;
  for(int i = n + 1 ; i <= 250000 ; i++)
    st.insert(i);
  map < int, int > mp;
  for(int i = 0 ; i < n ; i++){
    if (gondolaSeq[i] < mn){
      mn = gondolaSeq[i], idx = i;
    }
  }
  int intended = mn;
  if (intended > n)
    intended = 1;
  for(int i = 0 ; i < n ; i++){
    int cur = gondolaSeq[(i + idx) % n];
    if (cur != intended){
        mp[intended] = cur;
        f[cur] = intended;
        elements.insert(intended);
    }
    intended++;
    if (intended > n)
    intended -= n;
  }
  int j = 0;
  for(auto &it :st){
    if (elements.empty())
      break;
    if (f[it]){
      int z = now[f[it]];
      replacementSeq[j++] = z;
      elements.erase(f[it]);
    }
    else {
      int z = *elements.begin();
      replacementSeq[j] = now[z];
      now[z] = it;
      j++;
    }
  }
  return j;
}
int countReplacement(int n, int inputSeq[]){
  a= b= c= m = 0;
  memset(dp, -1, sizeof dp);
  int mn = 1e9;
  int idx = -1;
  for(int i = 0 ; i < n ; i++){
    if (inputSeq[i] < mn){
      mn = inputSeq[i], idx = i;
    }
  }
  int intended = mn;
  if (intended > n)
    intended = 1;
  vector < pair < int, int > > v;
  for(int i = 0 ; i < n ; i++){
    int cur = inputSeq[(i + idx) % n];
    if (cur != intended){
        v.push_back({cur, intended});
    }
    intended++;
    if (intended > n)
    intended -= n;
  }
  m = n;
  int x, y, z;
  x = y = z = 0;
  if (v.size()){
    x = v[0].second;
    a = v[0].first;
  }
  if (v.size() > 1){
    y = v[1].second;
    b = v[1].first;
  }
  if (v.size() > 2){
    z = v[2].second;
    c = v[2].first;
  }
  return solve(x, y, z, 1);
}

Compilation message

gondola.cpp: In function 'long long int solve(int, int, int, bool)':
gondola.cpp:16:7: warning: variable 'n_x' set but not used [-Wunused-but-set-variable]
   int n_x, n_y, n_z;
       ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 16 ms 2168 KB Output is correct
7 Correct 41 ms 3684 KB Output is correct
8 Correct 29 ms 3964 KB Output is correct
9 Correct 11 ms 1500 KB Output is correct
10 Correct 38 ms 4472 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 18 ms 2168 KB Output is correct
7 Correct 46 ms 3692 KB Output is correct
8 Correct 33 ms 3960 KB Output is correct
9 Correct 11 ms 1528 KB Output is correct
10 Correct 37 ms 4600 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 22 ms 2040 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 56 ms 4728 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13992 KB Output is correct
2 Correct 87 ms 13980 KB Output is correct
3 Correct 86 ms 14072 KB Output is correct
4 Correct 86 ms 14072 KB Output is correct
5 Correct 86 ms 14200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 14072 KB Output is correct
2 Correct 87 ms 14172 KB Output is correct
3 Correct 88 ms 13944 KB Output is correct
4 Correct 86 ms 13944 KB Output is correct
5 Correct 86 ms 14060 KB Output is correct
6 Correct 86 ms 14072 KB Output is correct
7 Correct 87 ms 14036 KB Output is correct
8 Correct 88 ms 14044 KB Output is correct
9 Correct 86 ms 14072 KB Output is correct
10 Correct 88 ms 14176 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 14064 KB Output is correct
2 Correct 86 ms 14072 KB Output is correct
3 Correct 87 ms 14072 KB Output is correct
4 Correct 86 ms 13980 KB Output is correct
5 Correct 86 ms 14200 KB Output is correct
6 Correct 86 ms 13948 KB Output is correct
7 Correct 87 ms 14072 KB Output is correct
8 Correct 87 ms 14072 KB Output is correct
9 Correct 87 ms 14160 KB Output is correct
10 Correct 91 ms 14072 KB Output is correct
11 Correct 68 ms 10616 KB Output is correct
12 Correct 65 ms 10104 KB Output is correct
13 Correct 116 ms 16092 KB Output is correct
14 Correct 68 ms 10616 KB Output is correct
15 Correct 117 ms 16648 KB Output is correct

Subtask #7
0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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