oj.uz

Submission #320971

# Submission time Handle Problem Language Result Execution time Memory
320971 2020-11-10T11:45:32 Z arnold518 Mechanical Doll (IOI18_doll) C++14
100 / 100
 156 ms 14916 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;

vector<int> V;
int N, M, A[MAXN+10];
int B[MAXN+10], X[MAXN+10], Y[MAXN+10], C[MAXN+10], ncnt;

int solve(int l, int r)
{
    bool flag=true;
    for(int i=l; i<=r; i++) if(B[i]!=-1) flag=false;
    if(flag) return -1;
    if(l==r) return B[l];
    int mid=l+r>>1;

    int node=++ncnt;
    X[node]=solve(l, mid);
    Y[node]=solve(mid+1, r);
    return -node;
}

void create_circuit(int _M, vector<int> _A)
{
    M=_M; N=_A.size();
    for(int i=0; i<N; i++) A[i]=_A[i];
    A[N]=0; N++;

    V.push_back(1);
    V.push_back(2);
    while(V.size()<N)
    {
        vector<int> VV;
        for(auto it : V) VV.push_back(it*2-1);
        for(auto it : V) VV.push_back(it*2);
        V=VV;
    }

    vector<pii> V2;
    for(int i=V.size()-N; i<V.size(); i++) V2.push_back({V[i], i});
    sort(V2.begin(), V2.end());
    for(int i=0; i<V2.size(); i++) B[V2[i].second]=A[i];
    for(int i=0; i<V.size()-N; i++) B[i]=-1;

    //for(int i=0; i<V.size(); i++) printf("%d ", B[i]); printf("\n");

    solve(0, V.size()-1);
    C[0]=-1;
    for(int i=1; i<=M; i++) C[i]=-1;

    vector<int> CC, XX, YY;
    for(int i=0; i<=M; i++) CC.push_back(C[i]);
    for(int i=1; i<=ncnt; i++) XX.push_back(X[i]);
    for(int i=1; i<=ncnt; i++) YY.push_back(Y[i]);

    //for(int i=1; i<=ncnt; i++) printf("%d : %d %d\n", i, X[i], Y[i]);

    answer(CC, XX, YY);
}

Compilation message

doll.cpp: In function 'int solve(int, int)':
doll.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid=l+r>>1;
      |             ~^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     while(V.size()<N)
      |           ~~~~~~~~^~
doll.cpp:46:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=V.size()-N; i<V.size(); i++) V2.push_back({V[i], i});
      |                           ~^~~~~~~~~
doll.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0; i<V2.size(); i++) B[V2[i].second]=A[i];
      |                  ~^~~~~~~~~~
doll.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0; i<V.size()-N; i++) B[i]=-1;
      |                  ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 6780 KB Output is correct
3 Correct 39 ms 6148 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1972 KB Output is correct
6 Correct 61 ms 8496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 6780 KB Output is correct
3 Correct 39 ms 6148 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1972 KB Output is correct
6 Correct 61 ms 8496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 78 ms 10912 KB Output is correct
9 Correct 78 ms 11296 KB Output is correct
10 Correct 120 ms 14916 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 6780 KB Output is correct
3 Correct 39 ms 6148 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1972 KB Output is correct
6 Correct 61 ms 8496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 78 ms 10912 KB Output is correct
9 Correct 78 ms 11296 KB Output is correct
10 Correct 120 ms 14916 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 117 ms 14600 KB Output is correct
15 Correct 73 ms 10040 KB Output is correct
16 Correct 114 ms 14348 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 156 ms 14756 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 63 ms 9568 KB Output is correct
3 Correct 72 ms 9528 KB Output is correct
4 Correct 119 ms 12804 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 63 ms 9568 KB Output is correct
3 Correct 72 ms 9528 KB Output is correct
4 Correct 119 ms 12804 KB Output is correct
5 Correct 111 ms 14296 KB Output is correct
6 Correct 106 ms 13272 KB Output is correct
7 Correct 146 ms 13352 KB Output is correct
8 Correct 112 ms 12992 KB Output is correct
9 Correct 66 ms 9544 KB Output is correct
10 Correct 128 ms 12936 KB Output is correct
11 Correct 140 ms 12728 KB Output is correct
12 Correct 80 ms 9548 KB Output is correct
13 Correct 82 ms 9764 KB Output is correct
14 Correct 89 ms 9772 KB Output is correct
15 Correct 70 ms 9868 KB Output is correct
16 Correct 4 ms 644 KB Output is correct
17 Correct 67 ms 8520 KB Output is correct
18 Correct 68 ms 9528 KB Output is correct
19 Correct 70 ms 9524 KB Output is correct
20 Correct 108 ms 12820 KB Output is correct
21 Correct 118 ms 12744 KB Output is correct
22 Correct 103 ms 12784 KB Output is correct