oj.uz

Submission #839165

# Submission time Handle Problem Language Result Execution time Memory
839165 2023-08-28T22:28:19 Z beaconmc Mechanical Doll (IOI18_doll) C++14
10.8004 / 100
 119 ms 13384 KB 
#include "doll.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef int ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)





vector<ll> binorder(ll n){
  if (n==0) return {0};
  vector<ll> ans;
  vector<ll> sus = binorder(n-1);
  for (auto&i : sus){
    ans.push_back(i*2);
  }
  for (auto&i : sus){
    ans.push_back(i*2 + 1);
  }
  return ans;
}



void create_circuit(int M, vector<int> A) {
  ll offset = 0;
  ll N = A.size();





  vector<ll> X;
  vector<ll> Y;
  vector<ll> ans;
  ans.push_back(-1);
  FOR(i, 1, M+1){
    ans.push_back(-1);
  }



  FOR(i, 0, 30){
    if (N < 2*(1<<i)){
      ll diff = 2*(1<<i)-N ;
      diff = (diff)/2;

      FOR(j,1, (1<<(i))){
        X.push_back(-j*2);
        Y.push_back(-j*2-1);
      }
      FOR(j, (1<<(i)), (1<<(i+1)) - diff){
        X.push_back(-1);
        Y.push_back(-1);
      }
      set<ll> replace;
      FOR(j, (1<<(i+1)) - diff, 1<<(i+1)){
        replace.insert(j);
        replace.insert(j-(1<<i));
      }

      vector<ll> order = binorder(i);
      vector<ll> order2 = binorder(i);
      for (auto&k : order2){
        order.push_back(k + (1<<i));
      }

      vector<ll> stuff2(1<<(i+1));

      FOR(j,0,order.size()){
        stuff2[order[j]] = j;
      }
      vector<ll> stuff;
      for (auto&j : stuff2){
        if (!replace.count(j)) stuff.push_back(j);
      }

      FOR(j,0,N){
        if (stuff[j] >= (1<<i)) Y[stuff[j]-1] = A[j];
        else X[stuff[j]+(1<<i)-1] = A[j];
      }
      ll comb = -(X.size()+1);
      ll final = -(X.size()+2);


      FOR(j,0,X.size()){
        if (X[j] <= -(1<<i) && replace.count(-X[j])) X[j] = comb;
      }

      FOR(j,0,Y.size()){

        if (Y[j] == -(1<<(i+1))+1){
          Y[j] = final + (diff==1);
          continue;
        }

        if (Y[j] <= -(1<<i) && replace.count(-Y[j])) Y[j] = comb;
      }

      if (diff == 1){
        X.push_back(-1);
        Y.push_back(-1);
      }else if (diff >= 2){
        X.push_back(-1);
        Y.push_back(-1);
        X.push_back(-1);
        Y.push_back(0);
      }





      break;

    }
  }
  Y[Y.size()-1] = 0;




  // for (auto&i : ans){
  //   cout << i << " ";
  // }cout << endl;
  // for (auto&i : X){
  //   cout << i << " ";

  // }cout << endl;

  // for (auto&i : Y){
  //   cout << i << " ";

  // }cout << endl;
  

  answer(ans, X, Y);


}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:10:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   79 |       FOR(j,0,order.size()){
      |           ~~~~~~~~~~~~~~~~         
doll.cpp:79:7: note: in expansion of macro 'FOR'
   79 |       FOR(j,0,order.size()){
      |       ^~~
doll.cpp:10:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   95 |       FOR(j,0,X.size()){
      |           ~~~~~~~~~~~~             
doll.cpp:95:7: note: in expansion of macro 'FOR'
   95 |       FOR(j,0,X.size()){
      |       ^~~
doll.cpp:10:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   99 |       FOR(j,0,Y.size()){
      |           ~~~~~~~~~~~~             
doll.cpp:99:7: note: in expansion of macro 'FOR'
   99 |       FOR(j,0,Y.size()){
      |       ^~~
doll.cpp:35:6: warning: unused variable 'offset' [-Wunused-variable]
   35 |   ll offset = 0;
      |      ^~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.800412065 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 119 ms 12828 KB Output is partially correct
3 Partially correct 105 ms 13288 KB Output is partially correct
4 Partially correct 92 ms 11192 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 119 ms 12828 KB Output is partially correct
3 Partially correct 105 ms 13288 KB Output is partially correct
4 Partially correct 92 ms 11192 KB Output is partially correct
5 Partially correct 95 ms 11460 KB Output is partially correct
6 Partially correct 99 ms 11288 KB Output is partially correct
7 Partially correct 93 ms 11320 KB Output is partially correct
8 Partially correct 100 ms 11412 KB Output is partially correct
9 Partially correct 115 ms 13296 KB Output is partially correct
10 Partially correct 92 ms 11192 KB Output is partially correct
11 Partially correct 92 ms 11184 KB Output is partially correct
12 Partially correct 110 ms 13272 KB Output is partially correct
13 Partially correct 109 ms 12940 KB Output is partially correct
14 Partially correct 112 ms 13384 KB Output is partially correct
15 Partially correct 111 ms 13368 KB Output is partially correct
16 Partially correct 3 ms 716 KB Output is partially correct
17 Incorrect 36 ms 4816 KB wrong serial number
18 Halted 0 ms 0 KB -