제출 #839166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839166		beaconmc	자동 인형 (IOI18_doll)	C++14	44.40 / 100	128 ms	13492 KiB

doll

#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){
          if (diff==1) Y[j] = comb;
          else if (diff == 0) continue;
          else 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);


}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10.800412065 / 18
• Subtask 6: 33.601281979999996 / 56