oj.uz

Submission #839164

# Submission time Handle Problem Language Result Execution time Memory
839164 2023-08-28T22:20:11 Z beaconmc Mechanical Doll (IOI18_doll) C++14
10.8004 / 100
 120 ms 13492 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 - 1;
      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 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 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.80035712 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 120 ms 13392 KB Output is partially correct
3 Partially correct 104 ms 13276 KB Output is partially correct
4 Partially correct 90 ms 11236 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 120 ms 13392 KB Output is partially correct
3 Partially correct 104 ms 13276 KB Output is partially correct
4 Partially correct 90 ms 11236 KB Output is partially correct
5 Partially correct 96 ms 11496 KB Output is partially correct
6 Partially correct 94 ms 11316 KB Output is partially correct
7 Partially correct 93 ms 11288 KB Output is partially correct
8 Partially correct 90 ms 11272 KB Output is partially correct
9 Partially correct 104 ms 13368 KB Output is partially correct
10 Partially correct 93 ms 11288 KB Output is partially correct
11 Partially correct 87 ms 11280 KB Output is partially correct
12 Partially correct 104 ms 13400 KB Output is partially correct
13 Partially correct 108 ms 13460 KB Output is partially correct
14 Partially correct 107 ms 13372 KB Output is partially correct
15 Partially correct 108 ms 13492 KB Output is partially correct
16 Partially correct 3 ms 716 KB Output is partially correct
17 Incorrect 30 ms 4824 KB wrong serial number
18 Halted 0 ms 0 KB -