oj.uz

Submission #138643

# Submission time Handle Problem Language Result Execution time Memory
138643 2019-07-30T07:59:20 Z Bohoty Gondola (IOI14_gondola) C++14
15 / 100
 43 ms 4932 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;
  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 256 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 256 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 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
6 Correct 16 ms 2324 KB Output is correct
7 Correct 38 ms 3704 KB Output is correct
8 Correct 32 ms 3932 KB Output is correct
9 Correct 10 ms 1400 KB Output is correct
10 Correct 43 ms 4600 KB Output is correct

Subtask #3
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 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 17 ms 2268 KB Output is correct
7 Correct 42 ms 3676 KB Output is correct
8 Correct 30 ms 3960 KB Output is correct
9 Correct 10 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 Incorrect 2 ms 256 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 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 256 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 256 KB Output is correct
5 Correct 2 ms 256 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 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
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 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 4932 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 4828 KB Output isn't correct
2 Halted 0 ms 0 KB -