Submission #1065527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065527		bleahbleah	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	13 ms	728 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace Query {
   map<pii, bool> prec;
   bool query(int a, int b) {
      if(a > b) swap(a, b);
      if(prec.count(pii{a, b})) return prec[pii{a, b}];
      vector<int> t[2];
      t[0].emplace_back(a);
      t[1].emplace_back(b);
      return prec[pii{a, b}] = are_connected(t[0], t[1]);
   }
   bool query(int a, vector<int> b) {
      vector<int> t[2];
      t[0].emplace_back(a);
      t[1] = b;
      return are_connected(t[0], t[1]);
   }
   bool query(vector<int> b, int a) {
      return query(a, b);
   }
   bool query(vector<int> a, vector<int> b) {
      return are_connected(a, b);
   }
};

std::vector<int> longest_trip(int N, int D) {
   Query::prec.clear();
   
   
   using namespace Query;
   vector<int> perm(N);
   iota(all(perm), 0);
   shuffle(all(perm), rng);
   vector<int> st[2];
   st[0].emplace_back(perm.back());
   perm.pop_back();
   bool certain = 0;
   
   for(auto x : perm) {
      if(sz(st[0]) < sz(st[1])) swap(st[0], st[1]);
      if(sz(st[0]) && sz(st[1]) && rng() % 2 == 0) swap(st[0], st[1]);
      
      //cerr << certain << '\t' << st[0].back() << ' ' << (sz(st[1])? st[1].back() : -1) << ' ' << x << '\n';
      
      if(sz(st[1]) == 0) st[1].emplace_back(x);
      else if(query(st[0].back(), x)) st[0].emplace_back(x), certain = 0;
      else {
         if(certain) st[1].emplace_back(x), certain = 0;
         else {
            if(query(st[1].back(), x))
               st[1].emplace_back(x), certain = 1;
            else {
               copy(rbegin(st[1]), rend(st[1]), back_inserter(st[0]));
               st[1].clear();
               if(query(st[0].back(), x)) st[0].emplace_back(x);
               else certain = 1, st[1].emplace_back(x);
            }
         }
      }
   }
   
   if(sz(st[1]) == 0) return st[0];
   if(sz(st[0]) == 0) return st[1]; // ???
   if(rng() % 2 == 0) swap(st[0], st[1]); // nu o sa aibe niciun efect lol
   
   //for(int i = 1; i < sz(st[0]); i++) assert(query(st[0][i], st[0][i - 1]));
   //for(int i = 1; i < sz(st[1]); i++) assert(query(st[1][i], st[1][i - 1]));
   
   //for(auto a : st[0]) cerr << a << ' '; cerr << '\n';
   //for(auto a : st[1]) cerr << a << ' '; cerr << '\n';
   
   if(query(st[0][0], st[1])) {
      if(query(st[0][0], st[1].back()));
      else if(query(st[0][0], st[1][0])) { reverse(all(st[1])); }
      else {
         int lim = 1;
         for(int i = 10; i >= 0; i--) {
            int cand = lim + (1 << i);
            if(cand >= sz(st[1]) - 1) continue; // scoate -1ul ffs
            if(!query(st[0][0], vector<int>(begin(st[1]), begin(st[1]) + cand))) lim = cand;
         }
         for(int i = 0; i < lim; i++) st[1].emplace_back(st[1][i]);
         st[1].erase(begin(st[1]), begin(st[1]) + lim);
         reverse(all(st[1]));
      }
      copy(all(st[0]), back_inserter(st[1]));
      return st[1];
   }
   
   else {
      if(!query(st[0], st[1])) return sz(st[0]) > sz(st[1])? st[0] : st[1];
      int lim = 0;
      for(int i = 10; i >= 0; i--) {
         int cand = lim + (1 << i);
         if(cand >= sz(st[1])) continue;
         if(query(st[0], vector<int>(begin(st[1]) + cand, end(st[1])))) lim = cand;
      }
      swap(st[1][0], st[1][lim]);
      if(query(st[0].back(), st[1][0]));
      else {
         lim = 1;
         for(int i = 10; i >= 0; i--) {
            int cand = lim + (1 << i);
            if(cand >= sz(st[0]) - 1) continue; // scoate -1ul ffs
            if(!query(st[1][0], vector<int>(begin(st[0]), begin(st[0]) + cand))) lim = cand;
         }
         for(int i = 0; i < lim; i++) st[0].emplace_back(st[0][i]);
         st[0].erase(begin(st[0]), begin(st[0]) + lim);
         reverse(all(st[0]));
      }
      copy(all(st[1]), back_inserter(st[0]));
      return st[0];
   }
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60