oj.uz

답안 #1077323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077323 2024-08-27T05:18:17 Z belgianbot 자동 인형 (IOI18_doll) C++17
62 / 100
 100 ms 16152 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first 
#define se second

using namespace std;

vector<vector<int>> adj;
vector<int> C, X, Y;

int cnt = -1;

void divide(vector<int> *a, int prev) {
    if (a->size() == 2) {
        X.pb((*a)[0]);
        Y.pb((*a)[1]);
        return;
    }

    vector<int> b, c;
    for (int i = 0; i < a->size(); i++) {
        if (i & 1) c.pb( (*a)[i]);
        else b.pb((*a)[i]);
    }
    if (b.size() > c.size()) {
        c.pb(b.back());
        b.back() = prev;
    }
    X.pb(cnt); cnt--; Y.pb(0); int n = Y.size();
    divide(&b, cnt + 1);
    Y[n - 1] = cnt; cnt--;
    divide(&c, cnt + 1);
}
void build(int x) {
    int n = adj[x].size();
    if (!n) adj[x].pb(0);
    if (n == 1) C[x] = adj[x][0];
    else if (n) {
        C[x] = cnt; cnt--;
        divide(&adj[x], cnt + 1);
    }

} 
void create_circuit(int M, vector<int> A) {
    if (M == 1) {
            int N = A.size();
    A.push_back(0);
    vector<int> C(M + 1, INT_MAX), X, Y;
    C[0] = A[0];
 
    int time = N - 1;
    vector<pair<int,int>> fact = {{1, 1}};
    int cnt = -1;
    while (time) {
        int next = 0;
        for (auto x : fact) {
            if (time % x.first == 0) {
                time -= x.first;
                next = x.first;
                X.push_back(x.second);
                if (cnt != -1) Y.push_back(cnt);
                else C[1] = cnt;
                cnt--;
                break;
            }
        }
        for (auto &x : fact) x.first += next;
        fact.push_back({next, cnt + 1});
    }
    if (cnt != -1) Y.push_back(0);
    else C[1] = 0;
    answer(C, X, Y);
    return;
    }
    int N = A.size();
    A.push_back(0);
    C.resize(M + 1);

    adj.resize(M + 1);
    adj[0].pb(A[0]); C[0] = A[0];
    for (int i = 1; i <= N; i++) adj[A[i-1]].pb(A[i]);

    for (int i = 1; i <= M; i++) build(i);

    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void divide(std::vector<int>*, int)':
doll.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < a->size(); i++) {
      |                     ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 18 ms 7512 KB Output is correct
3 Correct 14 ms 5204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 7004 KB Output is correct
6 Correct 20 ms 7988 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 18 ms 7512 KB Output is correct
3 Correct 14 ms 5204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 7004 KB Output is correct
6 Correct 20 ms 7988 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 30 ms 7916 KB Output is correct
9 Correct 31 ms 9544 KB Output is correct
10 Correct 42 ms 12336 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 18 ms 7512 KB Output is correct
3 Correct 14 ms 5204 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 7004 KB Output is correct
6 Correct 20 ms 7988 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 30 ms 7916 KB Output is correct
9 Correct 31 ms 9544 KB Output is correct
10 Correct 42 ms 12336 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 57 ms 13376 KB Output is correct
15 Correct 30 ms 6992 KB Output is correct
16 Correct 48 ms 10288 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 51 ms 12592 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 10 ms 1884 KB Output is correct
3 Correct 10 ms 1984 KB Output is correct
4 Correct 14 ms 2652 KB Output is correct

Subtask #6
28.0000000448 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 10 ms 1884 KB Output is correct
3 Correct 10 ms 1984 KB Output is correct
4 Correct 14 ms 2652 KB Output is correct
5 Partially correct 87 ms 14524 KB Output is partially correct
6 Partially correct 78 ms 15224 KB Output is partially correct
7 Partially correct 80 ms 14928 KB Output is partially correct
8 Partially correct 100 ms 15760 KB Output is partially correct
9 Partially correct 57 ms 9852 KB Output is partially correct
10 Partially correct 85 ms 14640 KB Output is partially correct
11 Partially correct 88 ms 16152 KB Output is partially correct
12 Partially correct 58 ms 9692 KB Output is partially correct
13 Partially correct 66 ms 9256 KB Output is partially correct
14 Partially correct 47 ms 9108 KB Output is partially correct
15 Partially correct 47 ms 8664 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Partially correct 43 ms 7708 KB Output is partially correct
18 Partially correct 47 ms 7500 KB Output is partially correct
19 Partially correct 54 ms 8136 KB Output is partially correct
20 Partially correct 68 ms 11640 KB Output is partially correct
21 Partially correct 73 ms 14040 KB Output is partially correct
22 Partially correct 58 ms 10828 KB Output is partially correct