oj.uz

Submission #978130

# Submission time Handle Problem Language Result Execution time Memory
978130 2024-05-08T21:52:20 Z FEDIKUS Mechanical Doll (IOI18_doll) C++17
100 / 100
 159 ms 23988 KB 
#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

vector<pair<int,int> > s;
vector<int> a;
int n;
int step;
vector<int> posetio;

int klk=1;
int resi(int l,int r,int br=0,int bit=0){
  if(l>n) return -1;
  if(l==r){
    posetio.push_back(br);
    return br;
  }
  
  int ja=-klk;
  klk++;
  s.push_back({-1,-1});
  
  int mid=l+(r-l)/2;
  int levi=resi(l,mid,br+(1<<bit),bit+1);
  int desni=resi(mid+1,r,br,bit+1);
  s[-ja-1]={desni,levi};

  return ja;
}

void create_circuit(int m, vector<int> _a) {
  a=_a;
  n=a.size();
  step=1;
  while(step<n+1) step*=2;
  int c=resi(0,step-1);
  vector<int> cc(m+1,c);
  vector<int> x(s.size()),y(s.size());
  sort(posetio.begin(),posetio.end());
  assert(int(posetio.size())==n+1);
  map<int,int> kurac;
  for(int i=0;i<n+1;i++){
    if(i==n) kurac[posetio[i]]=0;
    else kurac[posetio[i]]=a[i];
  }
  for(int i=0;i<int(s.size());i++){
    if(s[i].first<0) x[i]=s[i].first;
    else x[i]=kurac[s[i].first];
    if(s[i].second<0) y[i]=s[i].second;
    else y[i]=kurac[s[i].second];
  }
  answer(cc,x,y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 8972 KB Output is correct
3 Correct 41 ms 8376 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 73 ms 12848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 8972 KB Output is correct
3 Correct 41 ms 8376 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 73 ms 12848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 15748 KB Output is correct
9 Correct 87 ms 16320 KB Output is correct
10 Correct 149 ms 23988 KB Output is correct
11 Correct 0 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 43 ms 8972 KB Output is correct
3 Correct 41 ms 8376 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 73 ms 12848 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 15748 KB Output is correct
9 Correct 87 ms 16320 KB Output is correct
10 Correct 149 ms 23988 KB Output is correct
11 Correct 0 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 145 ms 23476 KB Output is correct
15 Correct 86 ms 15280 KB Output is correct
16 Correct 147 ms 23216 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 148 ms 23688 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 75 ms 14188 KB Output is correct
3 Correct 76 ms 14272 KB Output is correct
4 Correct 143 ms 21840 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 75 ms 14188 KB Output is correct
3 Correct 76 ms 14272 KB Output is correct
4 Correct 143 ms 21840 KB Output is correct
5 Correct 159 ms 22964 KB Output is correct
6 Correct 143 ms 22708 KB Output is correct
7 Correct 151 ms 22708 KB Output is correct
8 Correct 157 ms 23256 KB Output is correct
9 Correct 81 ms 14352 KB Output is correct
10 Correct 138 ms 22448 KB Output is correct
11 Correct 148 ms 22004 KB Output is correct
12 Correct 98 ms 14528 KB Output is correct
13 Correct 110 ms 14784 KB Output is correct
14 Correct 104 ms 15296 KB Output is correct
15 Correct 92 ms 15228 KB Output is correct
16 Correct 2 ms 700 KB Output is correct
17 Correct 80 ms 14468 KB Output is correct
18 Correct 80 ms 14452 KB Output is correct
19 Correct 85 ms 14448 KB Output is correct
20 Correct 151 ms 22176 KB Output is correct
21 Correct 152 ms 22028 KB Output is correct
22 Correct 147 ms 22196 KB Output is correct