oj.uz

답안 #138693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138693 2019-07-30T08:40:04 Z Bohoty 곤돌라 (IOI14_gondola) C++14
55 / 100
 127 ms 16860 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;
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 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 376 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 252 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 2424 KB Output is correct
7 Correct 39 ms 4216 KB Output is correct
8 Correct 30 ms 4400 KB Output is correct
9 Correct 10 ms 1656 KB Output is correct
10 Correct 37 ms 4984 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 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 Correct 17 ms 2424 KB Output is correct
7 Correct 41 ms 4228 KB Output is correct
8 Correct 25 ms 4344 KB Output is correct
9 Correct 10 ms 1656 KB Output is correct
10 Correct 38 ms 5112 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 3 ms 256 KB Output is correct
13 Correct 23 ms 2424 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 62 ms 5368 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 13952 KB Output is correct
2 Correct 87 ms 14072 KB Output is correct
3 Correct 87 ms 13944 KB Output is correct
4 Correct 86 ms 13948 KB Output is correct
5 Correct 89 ms 14200 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 14072 KB Output is correct
2 Correct 87 ms 13964 KB Output is correct
3 Correct 87 ms 14072 KB Output is correct
4 Correct 86 ms 13944 KB Output is correct
5 Correct 86 ms 14072 KB Output is correct
6 Correct 87 ms 14072 KB Output is correct
7 Correct 86 ms 13944 KB Output is correct
8 Correct 87 ms 14072 KB Output is correct
9 Correct 88 ms 14072 KB Output is correct
10 Correct 86 ms 14072 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 14172 KB Output is correct
2 Correct 107 ms 14132 KB Output is correct
3 Correct 90 ms 14048 KB Output is correct
4 Correct 87 ms 14028 KB Output is correct
5 Correct 86 ms 14072 KB Output is correct
6 Correct 86 ms 13960 KB Output is correct
7 Correct 88 ms 13944 KB Output is correct
8 Correct 86 ms 14072 KB Output is correct
9 Correct 87 ms 14204 KB Output is correct
10 Correct 87 ms 14072 KB Output is correct
11 Correct 67 ms 11128 KB Output is correct
12 Correct 71 ms 10744 KB Output is correct
13 Correct 117 ms 16376 KB Output is correct
14 Correct 69 ms 11128 KB Output is correct
15 Correct 127 ms 16860 KB Output is correct

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -