Submission #713771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713771	2023-03-23T03:26:49 Z	victor_gao	Mechanical Doll (IOI18_doll)	C++17	6 / 100	86 ms	20672 KB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>to[100015],g[100015];
vector<int>ans1,ans2,c;
int n,m,now=0;
int build(int num,int l,int r){
    if (l==r) return -g[num][l];
    int mid=(l+r)>>1,use=--now;
    use=abs(use);
    int p1=build(num,l,mid);
    ans1[use]=-p1;
    int p2=build(num,mid+1,r);
    ans2[use]=-p2;
    return use;
}
void create_circuit(int M, std::vector<int> A) {
    m=M;
    ans1.resize(400000); ans2.resize(400000);
    A.insert(A.begin(),0);
    A.push_back(0);
    n = A.size();
    for (int i=0;i<n-1;i++){
        to[A[i]].push_back(A[i+1]);
    }
    for (int i=0;i<=m;i++){
        if (to[i].empty()) continue;
        g[i].resize(to[i].size());
        int p=0;
        for (int j=0; ;j++){
            if ((1LL<<j)>=(int)to[i].size()){
                p=j;
                break;
            }
        }
        for (int j=0;j<to[i].size();j++){
            int idx=0;
            for (int k=0;k<p;k++){
                if (j&(1LL<<k))
                    idx=(idx+(1LL<<(p-k-1)));
            }
            g[i][idx]=to[i][j];
        }
    }
    c.resize(m+1);
    for (int i=0;i<=m;i++){
        if (g[i].empty()) c[i]=0;
        else if (g[i].size()==1) c[i]=g[i][0];
        else c[i]=-build(i,0,g[i].size()-1);
    }
    now=abs(now);
    vector<int>X,Y;
    for (int i=1;i<=now;i++){
        X.push_back(ans1[i]);
    }
    for (int i=1;i<=now;i++){
        Y.push_back(ans2[i]);
    }
    answer(c, X, Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8020 KB	Output is correct
2	Correct	38 ms	13904 KB	Output is correct
3	Correct	29 ms	13572 KB	Output is correct
4	Correct	4 ms	8020 KB	Output is correct
5	Correct	13 ms	9300 KB	Output is correct
6	Correct	44 ms	16452 KB	Output is correct
7	Correct	4 ms	8020 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8020 KB	Output is correct
2	Correct	38 ms	13904 KB	Output is correct
3	Correct	29 ms	13572 KB	Output is correct
4	Correct	4 ms	8020 KB	Output is correct
5	Correct	13 ms	9300 KB	Output is correct
6	Correct	44 ms	16452 KB	Output is correct
7	Correct	4 ms	8020 KB	Output is correct
8	Correct	52 ms	16516 KB	Output is correct
9	Correct	60 ms	17412 KB	Output is correct
10	Correct	86 ms	20672 KB	Output is correct
11	Correct	4 ms	8020 KB	Output is correct
12	Correct	4 ms	8020 KB	Output is correct
13	Correct	4 ms	8020 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	8020 KB	Output is correct
2	Correct	38 ms	13904 KB	Output is correct
3	Correct	29 ms	13572 KB	Output is correct
4	Correct	4 ms	8020 KB	Output is correct
5	Correct	13 ms	9300 KB	Output is correct
6	Correct	44 ms	16452 KB	Output is correct
7	Correct	4 ms	8020 KB	Output is correct
8	Correct	52 ms	16516 KB	Output is correct
9	Correct	60 ms	17412 KB	Output is correct
10	Correct	86 ms	20672 KB	Output is correct
11	Correct	4 ms	8020 KB	Output is correct
12	Correct	4 ms	8020 KB	Output is correct
13	Correct	4 ms	8020 KB	Output is correct
14	Incorrect	75 ms	17976 KB	state 'Y'
15	Halted	0 ms	0 KB	-