oj.uz

Submission #996301

# Submission time Handle Problem Language Result Execution time Memory
996301 2024-06-10T12:14:26 Z PCTprobability Mechanical Doll (IOI18_doll) C++17
100 / 100
 88 ms 17260 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int m, std::vector<int> a) {
  a.push_back(0);
  int n=a.size();
  vector<int> c(m+1);
  for(int i=0;i<=m;i++){
    c[i]=-1;
  }
  int nowi=2,s=1,bt=0;
  while(nowi<n){
    nowi*=2;
    s*=2;
    s++;
    bt++;
  }
  vector<int> x(s+1,-1),y(s+1,-1);
  int now=0;
  x[0]=0;
  y[0]=0;
  for(int i=1;i<=s;i++){
    if(i*2<=s){
      x[i]=-i*2;
      y[i]=-i*2-1;
    }
  }
  vector<pair<int,int>> pq;
  for(int i=0;i<(s+1)/2;i++){
    int id=0;
    for(int j=0;j<bt;j++){
      if((i>>j)&1) id^=(1<<(bt-1-j));
    }
    pq.push_back({id,i+(s+1)/2});
  }
  sort(pq.begin(),pq.end());
  vector<int> xs(s+1),ys(s+1);
  for(int i=0;i<pq.size();i++){
    xs[pq[i].second]=i;
    ys[pq[i].second]=i+(s+1)/2;
  }
  pq.clear();
  for(int i=s;i>=(s+1)/2;i--){
    if(pq.size()<a.size()){
      pq.push_back({xs[i],i});
    }
    if(pq.size()<a.size()){
      pq.push_back({ys[i],i});
    }
  }
  sort(pq.begin(),pq.end());
  //for(auto e:pq) cout<<e.first<<" "<<e.second<<endl;
  for(int i=0;i<pq.size();i++){
    //cout<<pq[i].second<<" "<<a[i]<<endl;
    if(x[pq[i].second]==-1){
      x[pq[i].second]=a[i];
    }
    else{
      y[pq[i].second]=a[i];
    }
  }
  /*for(auto e:x) cout<<e<<" ";
  cout<<endl;
  for(auto e:y) cout<<e<<" ";
  cout<<endl;*/
  vector<int> use(s+1);
  for(int i=s;i>=1;i--){
    if(x[i]>=0||y[i]>=0) continue;
    if((x[i]==-1||use[-x[i]]==-1)&&(y[i]==-1||use[-y[i]]==-1)){
      use[i]=-1;
    }
  }
  vector<int> nid(s+1,1);
  int z=1;
  for(int i=1;i<=s;i++){
    if(use[i]!=-1){
      nid[i]=z;
      z++;
    }
  }
  /*for(auto e:nid) cout<<e<<" ";
  cout<<endl;*/
  vector<int> X,Y;
  for(int i=1;i<=s;i++){
    if(use[i]!=-1){
      //cout<<i<<" "<<x[i]<<" "<<y[i]<<endl;
      if(x[i]>=0) X.push_back(x[i]);
      else X.push_back(-nid[-x[i]]);
      if(y[i]>=0) Y.push_back(y[i]);
      else Y.push_back(-nid[-y[i]]);
    }
  }
  /*for(auto e:x) cout<<e<<" ";
  cout<<endl;
  for(auto e:y) cout<<e<<" ";
  cout<<endl;
  for(auto e:X) cout<<e<<" ";
  cout<<endl;
  for(auto e:Y) cout<<e<<" ";
  cout<<endl;*/
  answer(c,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0;i<pq.size();i++){
      |               ~^~~~~~~~~~
doll.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0;i<pq.size();i++){
      |               ~^~~~~~~~~~
doll.cpp:19:7: warning: unused variable 'now' [-Wunused-variable]
   19 |   int now=0;
      |       ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 7892 KB Output is correct
3 Correct 29 ms 7640 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1624 KB Output is correct
6 Correct 49 ms 9672 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 7892 KB Output is correct
3 Correct 29 ms 7640 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1624 KB Output is correct
6 Correct 49 ms 9672 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 53 ms 13524 KB Output is correct
9 Correct 61 ms 14024 KB Output is correct
10 Correct 77 ms 17260 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 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 1 ms 344 KB Output is correct
2 Correct 30 ms 7892 KB Output is correct
3 Correct 29 ms 7640 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1624 KB Output is correct
6 Correct 49 ms 9672 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 53 ms 13524 KB Output is correct
9 Correct 61 ms 14024 KB Output is correct
10 Correct 77 ms 17260 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 73 ms 16700 KB Output is correct
15 Correct 58 ms 13000 KB Output is correct
16 Correct 71 ms 16448 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 77 ms 16888 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 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 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 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 51 ms 13008 KB Output is correct
3 Correct 51 ms 13008 KB Output is correct
4 Correct 71 ms 16444 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 51 ms 13008 KB Output is correct
3 Correct 51 ms 13008 KB Output is correct
4 Correct 71 ms 16444 KB Output is correct
5 Correct 71 ms 16412 KB Output is correct
6 Correct 88 ms 16444 KB Output is correct
7 Correct 73 ms 16396 KB Output is correct
8 Correct 73 ms 16384 KB Output is correct
9 Correct 48 ms 13008 KB Output is correct
10 Correct 77 ms 16268 KB Output is correct
11 Correct 68 ms 16412 KB Output is correct
12 Correct 53 ms 12808 KB Output is correct
13 Correct 53 ms 13004 KB Output is correct
14 Correct 53 ms 12868 KB Output is correct
15 Correct 53 ms 13004 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 39 ms 10316 KB Output is correct
18 Correct 52 ms 13008 KB Output is correct
19 Correct 50 ms 12784 KB Output is correct
20 Correct 68 ms 16332 KB Output is correct
21 Correct 70 ms 16448 KB Output is correct
22 Correct 72 ms 16444 KB Output is correct