fork download
copy 
  1. #include "monster.h"
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. vector<int> Solve(int N) {
  7.   int query_count = 0;
  8.   map<pair<int, int>, int> memo;
  9.   const auto Compare = [&](int a, int b) {
  10.     if (memo.count({a, b})) return memo[{a, b}];
  11.     query_count++;
  12.     int foo = Query(a, b);
  13.     memo[{a, b}] = foo;
  14.     memo[{b, a}] = 1 - foo;
  15.     return foo;
  16.   };
  17.  
  18.   const auto MergeSort = [&](const auto &self, int l, int r) -> vector<int> {
  19.     if (l == r) return {l};
  20.     int md = (l + r) / 2;
  21.     vector<int> lft = self(self, l, md);
  22.     vector<int> rgt = self(self, md + 1, r);
  23.  
  24.     vector<int> res;
  25.     reverse(begin(lft), end(lft));
  26.     reverse(begin(rgt), end(rgt));
  27.  
  28.     while (!lft.empty() && !rgt.empty()) {
  29.       if (Compare(lft.back(), rgt.back())) {
  30.         res.emplace_back(lft.back());
  31.         lft.pop_back();
  32.       } else {
  33.         res.emplace_back(rgt.back());
  34.         rgt.pop_back();
  35.       }
  36.     }
  37.     while (!lft.empty()) {
  38.       res.emplace_back(lft.back());
  39.       lft.pop_back();
  40.     }
  41.     while (!rgt.empty()) {
  42.       res.emplace_back(rgt.back());
  43.       rgt.pop_back();
  44.     }
  45.  
  46.     return res;
  47.   };
  48.  
  49.   vector<int> almostSorted = MergeSort(MergeSort, 0, N - 1);
  50.  
  51.   const auto FindMaxSpecial = [&](int start) -> int {
  52.     for (int i = start + 1; i + 2 < N; i++) {
  53.       if (Compare(almostSorted[i], almostSorted[i + 2])) {
  54.         return i + 1;
  55.       }
  56.     }
  57.     return N - 1;
  58.   };
  59.  
  60.   vector<int> sorted;
  61.   vector<int> done(N);
  62.  
  63.   int mxId = -1;
  64.   int last = 0;
  65.  
  66.   if (Compare(almostSorted[0], almostSorted[2])) {
  67.     // - 3 4 1 2 ..
  68.     // - 3 0 1 2 ..
  69.     if (Compare(almostSorted[1], almostSorted[3])) {
  70.       mxId = 1;
  71.     } else {
  72.       mxId = 0;
  73.     }
  74.   } else {
  75.     // - 3 4 5 6 ...
  76.     // - 3 4 5 2 ...
  77.     // - 3 4 5 0 ...
  78.     // - 3 1 2 0 ...
  79.     // - 3 4 2 0 ...
  80.     if (Compare(almostSorted[0], almostSorted[3])) {
  81.       // - 3 4 5 0 ...
  82.       // - 3 1 2 0 ...
  83.       // - 3 4 2 0 ...
  84.       if (Compare(almostSorted[1], almostSorted[3])) {
  85.         // - 3 4 5 0 1
  86.         // - 3 4 5 1 2 ...
  87.         // - 3 4 2 0 1 ...
  88.         // - 4 5 3 0 1 ...
  89.         // - 4 2 3 0 1 ...
  90.         assert(N >= 5);
  91.         if (!Compare(almostSorted[1], almostSorted[4])) {
  92.           // - 5 3 4 1 2 ...
  93.           mxId = 4;
  94.           last = 3;
  95.           done[0] = done[1] = done[2] = 1;
  96.           sorted.emplace_back(almostSorted[0]);
  97.           sorted.emplace_back(almostSorted[2]);
  98.           sorted.emplace_back(almostSorted[1]);
  99.         } else if (Compare(almostSorted[2], almostSorted[4])) {
  100.           // - 3 4 5 0 1 ...
  101.           // - 3 4 5 1 2 ...
  102.           // - 4 5 3 0 1 ...
  103.           // - 5 3 4 0 1 ...
  104.           if (Compare(almostSorted[0], almostSorted[4])) {
  105.             // - 3 4 5 0 1 2 ...
  106.             // - 4 5 3 0 1 2 ...
  107.             // - 5 3 4 0 1 2 ...
  108.             assert(N >= 6);
  109.             last = 3;
  110.             mxId = FindMaxSpecial(3);
  111.             if (!Compare(almostSorted[0], almostSorted[mxId])) {
  112.               // - 3 4 5 0 1 2 ...
  113.               done[0] = done[1] = done[2] = 1;
  114.               sorted.emplace_back(almostSorted[2]);
  115.               sorted.emplace_back(almostSorted[1]);
  116.               sorted.emplace_back(almostSorted[0]);
  117.             } else if (!Compare(almostSorted[1], almostSorted[mxId])) {
  118.               // - 5 3 4 0 1 2 ...
  119.               done[0] = done[1] = done[2] = 1;
  120.               sorted.emplace_back(almostSorted[0]);
  121.               sorted.emplace_back(almostSorted[2]);
  122.               sorted.emplace_back(almostSorted[1]);
  123.             } else if (!Compare(almostSorted[2], almostSorted[mxId])) {
  124.               // - 4 5 3 0 1 2 ...
  125.               done[0] = done[1] = done[2] = 1;
  126.               sorted.emplace_back(almostSorted[1]);
  127.               sorted.emplace_back(almostSorted[0]);
  128.               sorted.emplace_back(almostSorted[2]);
  129.             }
  130.           } else {
  131.             // - 3 4 5 1 2 ...
  132.             mxId = 2;
  133.           }
  134.         } else {
  135.           // - 3 4 2 0 1 ...
  136.           mxId = 1;
  137.         }
  138.       } else {
  139.         // - 3 1 2 0 ...
  140.         mxId = 0;
  141.       }
  142.     } else {
  143.       // - 3 4 5 6 ...
  144.       // - 3 4 5 2 ...
  145.       mxId = FindMaxSpecial(0);
  146.     }
  147.   }
  148.  
  149.   for (int i = mxId; i >= 0; i--) if (!done[i]) {
  150.     done[i] = 1;
  151.     sorted.emplace_back(almostSorted[i]);
  152.   }
  153.   for (int i = mxId + 1; i < N; i++) {
  154.     if (!Compare(almostSorted[last], almostSorted[i])) {
  155.       last = i;
  156.       while (!done[last]) {
  157.         done[last] = 1;
  158.         sorted.emplace_back(almostSorted[last]);
  159.         last--;
  160.       }
  161.       last++;
  162.     }
  163.   }
  164.  
  165.   assert(sorted.size() == N);
  166.   vector<int> ans(N);
  167.   for (int i = 0; i < N; i++) {
  168.     ans[sorted[i]] = i;
  169.   }
  170.   for (int i = 0; i < N; i++) {
  171.     ans[i] = N - 1 - ans[i];
  172.   }
  173.   return ans;
  174. }
  175.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:10: fatal error: monster.h: No such file or directory
 #include "monster.h"
          ^~~~~~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/MGy0m1
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!