oj.uz

Submission #623903

# Submission time Handle Problem Language Result Execution time Memory
623903 2022-08-06T22:10:12 Z TimDee Mechanical Doll (IOI18_doll) C++17
100 / 100
 129 ms 11296 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int n, maxsz, maxh;
vector<int> c,x,y,a,s;
int cnt=0;

void build(int i, int h) {
  if (h==maxh-1) {x[i]=1e9+7, y[i]=1e9+7; return;}
  if (cnt==maxsz-1) return;
  y[i]=-(++cnt+1);
  build(cnt,h+1);
  if (cnt==maxsz-1) return;
  x[i]=-(++cnt+1);
  build(cnt,h+1);
}

void create_circuit(int m, vector<int>A) {

  n=A.size();
  c.assign(m+1,-1); c[0]=A[0];
  for(int i=1; i<n; ++i) a.push_back(A[i]); a.push_back(0);
  int lg=0; int X=n; while (X>>=1) lg++;
  maxsz=n+lg;
  maxh=lg+1;
  x.assign(maxsz,-1);
  y.assign(maxsz,-1);
  s.assign(maxsz,0);
  build(0,0);

  int have=0;
  for(int i=0; i<maxsz; ++i) {
    if (x[i]==1e9+7) have+=2;
  }

  while (have-n) {
    int i=0;
    while (1) {
      if (s[i]) {
        s[i]^=1;
        if (y[i]==1e9+7) {
          y[i]=-1;
          break;
        }
        i=-y[i]-1;
      } else {
        s[i]^=1;
        if (x[i]==1e9+7) {
          x[i]=-1;
          break;
        }
        i=-x[i]-1;
      }
    }
    --have;
  }

  for (auto v:a) {
    int i=0;
    while (1) {
      //cout<<i<<"->"; int ok; cin>>ok;
      if (s[i]) {
        s[i]^=1;
        if (y[i]==1e9+7) {
          y[i]=v;
          break;
        }
        i=-y[i]-1;
      } else {
        s[i]^=1;
        if (x[i]==1e9+7) {
          x[i]=v;
          break;
        }
        i=-x[i]-1;
      }
    }
  }

  for(int i=0; i<maxsz; ++i) {
    //cout<<-i-1<<" -> ["<<x[i]<<','<<y[i]<<"]\n";
  }

  answer(c,x,y);

}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:23:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |   for(int i=1; i<n; ++i) a.push_back(A[i]); a.push_back(0);
      |   ^~~
doll.cpp:23:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |   for(int i=1; i<n; ++i) a.push_back(A[i]); a.push_back(0);
      |                                             ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4184 KB Output is correct
3 Correct 38 ms 4320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 62 ms 5540 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4184 KB Output is correct
3 Correct 38 ms 4320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 62 ms 5540 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 75 ms 7516 KB Output is correct
9 Correct 74 ms 8928 KB Output is correct
10 Correct 116 ms 11296 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4184 KB Output is correct
3 Correct 38 ms 4320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 62 ms 5540 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 75 ms 7516 KB Output is correct
9 Correct 74 ms 8928 KB Output is correct
10 Correct 116 ms 11296 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 121 ms 10852 KB Output is correct
15 Correct 72 ms 7896 KB Output is correct
16 Correct 114 ms 10576 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 123 ms 11044 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 70 ms 5564 KB Output is correct
3 Correct 58 ms 6064 KB Output is correct
4 Correct 129 ms 8200 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 70 ms 5564 KB Output is correct
3 Correct 58 ms 6064 KB Output is correct
4 Correct 129 ms 8200 KB Output is correct
5 Correct 111 ms 10492 KB Output is correct
6 Correct 111 ms 10092 KB Output is correct
7 Correct 110 ms 10296 KB Output is correct
8 Correct 110 ms 9928 KB Output is correct
9 Correct 63 ms 6972 KB Output is correct
10 Correct 106 ms 9920 KB Output is correct
11 Correct 105 ms 9664 KB Output is correct
12 Correct 70 ms 7344 KB Output is correct
13 Correct 72 ms 6684 KB Output is correct
14 Correct 62 ms 7708 KB Output is correct
15 Correct 63 ms 7868 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 66 ms 6468 KB Output is correct
18 Correct 70 ms 6500 KB Output is correct
19 Correct 63 ms 7256 KB Output is correct
20 Correct 108 ms 9768 KB Output is correct
21 Correct 105 ms 9664 KB Output is correct
22 Correct 107 ms 9696 KB Output is correct