oj.uz

Submission #138650

# Submission time Handle Problem Language Result Execution time Memory
138650 2019-07-30T08:04:30 Z Bohoty Gondola (IOI14_gondola) C++14
25 / 100
 52 ms 4984 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;
  map < int, int > mp;
  for(int i = 0 ; i < n ; i++){
    if (gondolaSeq[i] < mn){
      mn = gondolaSeq[i], idx = i;
    }
  }
  int intended = mn;
  for(int i = 0 ; i < n ; i++){
    int cur = gondolaSeq[(i + idx) % n];
    if (cur != intended){
        mp[intended] = cur;
    }
    intended++;
    if (intended > n)
    intended -= n;
  }
  int l = mp.size();
  int j = 0;
  for(auto it : mp){
    replacementSeq[j++] = it.first;
  }
  return l;
}
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;
  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 380 KB Output is correct
2 Correct 2 ms 256 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

Subtask #2
5.0 / 5.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 348 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 17 ms 2424 KB Output is correct
7 Correct 40 ms 4072 KB Output is correct
8 Correct 29 ms 4216 KB Output is correct
9 Correct 10 ms 1660 KB Output is correct
10 Correct 39 ms 4856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
6 Correct 16 ms 2424 KB Output is correct
7 Correct 39 ms 3960 KB Output is correct
8 Correct 29 ms 4216 KB Output is correct
9 Correct 10 ms 1528 KB Output is correct
10 Correct 36 ms 4840 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 2296 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 52 ms 4984 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
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 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 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 5 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 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -