oj.uz

Submission #839163

# Submission time Handle Problem Language Result Execution time Memory
839163 2023-08-28T22:18:41 Z beaconmc Mechanical Doll (IOI18_doll) C++14
10.8004 / 100
 122 ms 13556 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;
          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++)
......
   94 |       FOR(j,0,X.size()){
      |           ~~~~~~~~~~~~             
doll.cpp:94:7: note: in expansion of macro 'FOR'
   94 |       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++)
......
   98 |       FOR(j,0,Y.size()){
      |           ~~~~~~~~~~~~             
doll.cpp:98:7: note: in expansion of macro 'FOR'
   98 |       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 0 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 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 0 ms 336 KB Output is partially correct
2 Partially correct 108 ms 12876 KB Output is partially correct
3 Partially correct 106 ms 13396 KB Output is partially correct
4 Partially correct 88 ms 11236 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 336 KB Output is partially correct
2 Partially correct 108 ms 12876 KB Output is partially correct
3 Partially correct 106 ms 13396 KB Output is partially correct
4 Partially correct 88 ms 11236 KB Output is partially correct
5 Partially correct 95 ms 11364 KB Output is partially correct
6 Partially correct 93 ms 11192 KB Output is partially correct
7 Partially correct 96 ms 11320 KB Output is partially correct
8 Partially correct 90 ms 11284 KB Output is partially correct
9 Partially correct 106 ms 13396 KB Output is partially correct
10 Partially correct 89 ms 11192 KB Output is partially correct
11 Partially correct 89 ms 11236 KB Output is partially correct
12 Partially correct 106 ms 13356 KB Output is partially correct
13 Partially correct 111 ms 12820 KB Output is partially correct
14 Partially correct 122 ms 13556 KB Output is partially correct
15 Partially correct 109 ms 13388 KB Output is partially correct
16 Partially correct 2 ms 716 KB Output is partially correct
17 Incorrect 36 ms 4728 KB wrong serial number
18 Halted 0 ms 0 KB -