oj.uz

Submission #972827

# Submission time Handle Problem Language Result Execution time Memory
972827 2024-05-01T08:36:32 Z kwongweng Mechanical Doll (IOI18_doll) C++17
53 / 100
 125 ms 22328 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

const int mxN = 1e6+1;
int cur = 1; vi X(mxN),Y(mxN),C;

void build(int i, vi nxt){
  if (nxt.size()==2){
    X[i-1] = nxt[0];
    Y[i-1] = nxt[1];
    return;
  }
  int len = nxt.size();
  if (len % 2 == 0){
    X[i-1] = -cur; cur++;
    vi Nxt;
    for (int j = 0; j < len; j+=2) Nxt.pb(nxt[j]);
    build(cur-1,Nxt); Nxt.clear();
    for (int j = 1; j < len; j+=2) Nxt.pb(nxt[j]);
    Y[i-1] = -cur; cur++;
    build(cur-1,Nxt);
  }else{
    X[i-1] = -cur; cur++;
    vi Nxt;
    for (int j = 0; j < len-1; j+=2) Nxt.pb(nxt[j]);
    Nxt.pb(-i);
    build(cur-1,Nxt); Nxt.clear();
    for (int j = 1; j < len; j+=2) Nxt.pb(nxt[j]);
    Y[i-1] = -cur; cur++; 
    Nxt.pb(nxt[len-1]);
    build(cur-1,Nxt);
  }
}
void create_circuit(int M, vi A) {
  int N = A.size();
  C.resize(M+1);
  C[0] = A[0];
  vi nxt[M+1];
  FOR(i,0,N-1){
    nxt[A[i]].pb(A[i+1]);
  }
  nxt[A[N-1]].pb(0);
  FOR(i,1,M+1){
    if (nxt[i].empty()) continue;
    if (nxt[i].size()==1){
      C[i] = nxt[i][0]; continue;
    }
    C[i] = -cur; cur++;
    build(cur-1,nxt[i]);
  }
  vi x(cur-1), y(cur-1);
  FOR(i,0,cur-1){
    x[i]=X[i]; y[i]=Y[i];
  }
  answer(C, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 22 ms 14684 KB Output is correct
3 Correct 17 ms 13520 KB Output is correct
4 Correct 3 ms 8280 KB Output is correct
5 Correct 10 ms 11608 KB Output is correct
6 Correct 26 ms 16220 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 22 ms 14684 KB Output is correct
3 Correct 17 ms 13520 KB Output is correct
4 Correct 3 ms 8280 KB Output is correct
5 Correct 10 ms 11608 KB Output is correct
6 Correct 26 ms 16220 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 35 ms 16048 KB Output is correct
9 Correct 36 ms 17500 KB Output is correct
10 Correct 60 ms 20300 KB Output is correct
11 Correct 4 ms 8280 KB Output is correct
12 Correct 2 ms 8280 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 22 ms 14684 KB Output is correct
3 Correct 17 ms 13520 KB Output is correct
4 Correct 3 ms 8280 KB Output is correct
5 Correct 10 ms 11608 KB Output is correct
6 Correct 26 ms 16220 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 35 ms 16048 KB Output is correct
9 Correct 36 ms 17500 KB Output is correct
10 Correct 60 ms 20300 KB Output is correct
11 Correct 4 ms 8280 KB Output is correct
12 Correct 2 ms 8280 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 69 ms 20564 KB Output is correct
15 Correct 37 ms 14684 KB Output is correct
16 Correct 57 ms 17924 KB Output is correct
17 Correct 2 ms 8280 KB Output is correct
18 Correct 2 ms 8028 KB Output is correct
19 Correct 3 ms 8028 KB Output is correct
20 Correct 67 ms 19900 KB Output is correct
21 Correct 3 ms 8280 KB Output is correct
22 Correct 3 ms 8280 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 8024 KB Output is partially correct
2 Correct 45 ms 14328 KB Output is correct
3 Partially correct 67 ms 17208 KB Output is partially correct
4 Partially correct 84 ms 19636 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 8024 KB Output is partially correct
2 Correct 45 ms 14328 KB Output is correct
3 Partially correct 67 ms 17208 KB Output is partially correct
4 Partially correct 84 ms 19636 KB Output is partially correct
5 Partially correct 83 ms 21328 KB Output is partially correct
6 Partially correct 93 ms 21900 KB Output is partially correct
7 Partially correct 125 ms 21588 KB Output is partially correct
8 Partially correct 105 ms 21920 KB Output is partially correct
9 Partially correct 70 ms 17680 KB Output is partially correct
10 Partially correct 99 ms 21904 KB Output is partially correct
11 Partially correct 119 ms 22328 KB Output is partially correct
12 Partially correct 65 ms 17492 KB Output is partially correct
13 Partially correct 60 ms 16976 KB Output is partially correct
14 Partially correct 59 ms 16984 KB Output is partially correct
15 Partially correct 55 ms 16732 KB Output is partially correct
16 Partially correct 4 ms 8536 KB Output is partially correct
17 Partially correct 54 ms 15804 KB Output is partially correct
18 Partially correct 54 ms 15704 KB Output is partially correct
19 Partially correct 59 ms 16212 KB Output is partially correct
20 Partially correct 75 ms 19028 KB Output is partially correct
21 Partially correct 89 ms 20792 KB Output is partially correct
22 Partially correct 75 ms 18340 KB Output is partially correct