oj.uz

Submission #839161

# Submission time Handle Problem Language Result Execution time Memory
839161 2023-08-28T22:17:40 Z beaconmc Mechanical Doll (IOI18_doll) C++14
0 / 100
 1 ms 336 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));
      }
      for (auto&i : replace) cout << i << " ";
        cout << endl;

      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;
          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++)
......
   81 |       FOR(j,0,order.size()){
      |           ~~~~~~~~~~~~~~~~         
doll.cpp:81:7: note: in expansion of macro 'FOR'
   81 |       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++)
......
   96 |       FOR(j,0,X.size()){
      |           ~~~~~~~~~~~~             
doll.cpp:96:7: note: in expansion of macro 'FOR'
   96 |       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++)
......
  100 |       FOR(j,0,Y.size()){
      |           ~~~~~~~~~~~~             
doll.cpp:100:7: note: in expansion of macro 'FOR'
  100 |       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 336 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -