oj.uz

Submission #587140

# Submission time Handle Problem Language Result Execution time Memory
587140 2022-07-01T11:30:49 Z wdjpng Mechanical Doll (IOI18_doll) C++17
100 / 100
 150 ms 16368 KB 
#include <bits/stdc++.h>
#include "doll.h"

#define int long long
#define all(a) a.begin(), a.end()
#define rep(i,n) for(int i = 0; i<n; i++)

using namespace std;

vector<signed>x,y;
int pow2=1;
int cs = 0, ct = 1;
vector<pair<int,int>>ind(4e5+2);
int build(int l, int r, vector<signed>&a)
{
  if(r<=pow2-a.size()) return -1;
  if(l+1==r) return ct++;
  cs++;
  int ccs = -cs; 
  ind[ccs+4e5].first = build(l,(l+r)/2,a); 
  ind[ccs+4e5].second = build((l+r)/2,r,a); 
  return ccs;
}

int cntr = 0;
vector<bool>flip(4e5+2,false);
int sim(int cs, vector<signed>&a)
{
  if(cs>0) return a[cntr++];
  flip[cs+4e5]=!flip[cs+4e5];

  if(flip[cs+4e5]) x[-cs-1]=sim(ind[cs+4e5].first,a);
  else y[-cs-1]=sim(ind[cs+4e5].second,a); 

  return cs;
}

void create_circuit(signed m, vector<signed> a) {
  signed n = a.size();
  vector<signed>c(m+1);

  c[0]=a[0];
  if(n==1)
  {
    c[a[0]]=0;
    return answer(c,{},{});
  }
  a.push_back(0);
  a.erase(a.begin(), a.begin()+1);

  while (pow2<a.size()) pow2*=2;
  
  rep(i,m) c[i+1]=-1;
  build(0,pow2,a);
  x.assign(cs,1e9);
  y.assign(cs,1e9);

  rep(i,n) sim(-1,a);
  answer(c,x,y);
}

Compilation message

doll.cpp: In function 'long long int build(long long int, long long int, std::vector<int>&)':
doll.cpp:16:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   16 |   if(r<=pow2-a.size()) return -1;
      |      ~^~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:51:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   while (pow2<a.size()) pow2*=2;
      |          ~~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 46 ms 9920 KB Output is correct
3 Correct 49 ms 9936 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 14 ms 7764 KB Output is correct
6 Correct 68 ms 11628 KB Output is correct
7 Correct 3 ms 6612 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 46 ms 9920 KB Output is correct
3 Correct 49 ms 9936 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 14 ms 7764 KB Output is correct
6 Correct 68 ms 11628 KB Output is correct
7 Correct 3 ms 6612 KB Output is correct
8 Correct 83 ms 12500 KB Output is correct
9 Correct 95 ms 12884 KB Output is correct
10 Correct 134 ms 15736 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 3 ms 6624 KB Output is correct
13 Correct 3 ms 6612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 46 ms 9920 KB Output is correct
3 Correct 49 ms 9936 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 14 ms 7764 KB Output is correct
6 Correct 68 ms 11628 KB Output is correct
7 Correct 3 ms 6612 KB Output is correct
8 Correct 83 ms 12500 KB Output is correct
9 Correct 95 ms 12884 KB Output is correct
10 Correct 134 ms 15736 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 3 ms 6624 KB Output is correct
13 Correct 3 ms 6612 KB Output is correct
14 Correct 135 ms 16204 KB Output is correct
15 Correct 90 ms 12916 KB Output is correct
16 Correct 138 ms 15984 KB Output is correct
17 Correct 3 ms 6612 KB Output is correct
18 Correct 3 ms 6620 KB Output is correct
19 Correct 3 ms 6612 KB Output is correct
20 Correct 149 ms 16368 KB Output is correct
21 Correct 3 ms 6612 KB Output is correct
22 Correct 3 ms 6612 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 85 ms 11348 KB Output is correct
3 Correct 85 ms 11340 KB Output is correct
4 Correct 129 ms 13936 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 85 ms 11348 KB Output is correct
3 Correct 85 ms 11340 KB Output is correct
4 Correct 129 ms 13936 KB Output is correct
5 Correct 136 ms 15624 KB Output is correct
6 Correct 135 ms 15436 KB Output is correct
7 Correct 147 ms 15604 KB Output is correct
8 Correct 150 ms 15272 KB Output is correct
9 Correct 96 ms 11784 KB Output is correct
10 Correct 131 ms 15104 KB Output is correct
11 Correct 123 ms 14752 KB Output is correct
12 Correct 92 ms 12116 KB Output is correct
13 Correct 81 ms 12548 KB Output is correct
14 Correct 88 ms 12612 KB Output is correct
15 Correct 108 ms 12760 KB Output is correct
16 Correct 5 ms 6740 KB Output is correct
17 Correct 78 ms 12112 KB Output is correct
18 Correct 77 ms 12104 KB Output is correct
19 Correct 83 ms 12096 KB Output is correct
20 Correct 137 ms 14984 KB Output is correct
21 Correct 136 ms 14724 KB Output is correct
22 Correct 140 ms 14964 KB Output is correct