QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#396532	#4208. Flight to the Ford	hos_lyric	100 ✓	38ms	4120kb	C++14	4.0kb	2024-04-22 21:10:33	2024-04-22 21:10:33

Judging History

你现在查看的是最新测评结果

[2024-04-22 21:10:33]
评测

测评结果：100
用时：38ms
内存：4120kb

查看

[2024-04-22 21:10:33]
提交

answer

#include"communication.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


pair<int, int> solve(int N, int X) {
  // pss[1]: last was lie
  vector<pair<int, int>> pss[2];
  pss[0].emplace_back(1, N + 1);
  for (; ; ) {
    int tots[2] = {};
    for (int i = 0; i < 2; ++i) {
      for (const auto &p : pss[i]) {
        tots[i] += (p.second - p.first);
      }
    }
// cerr<<tots[0]<<" "<<tots[1]<<" "<<pss[0]<<" "<<pss[1]<<endl;
    if (tots[0] + tots[1] <= 3) {
      break;
    }
    vector<pair<int, int>> qsss[2][2];
    for (int i = 0; i < 2; ++i) {
      int lots[2] = {tots[i] / 2, (tots[i] + 1) / 2};
      if (i) swap(lots[0], lots[1]);
      for (const auto &p : pss[i]) {
        int l = p.first, r = p.second;
        for (int j = 0; j < 2; ++j) {
          const int t = min(r - l, lots[j]);
          if (t) {
            qsss[i][j].emplace_back(l, l + t);
            l += t;
            lots[j] -= t;
          }
        }
        assert(l == r);
      }
      assert(!lots[0]);
      assert(!lots[1]);
      pss[i].clear();
    }
    int r = -1;
    if (~X) {
      for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
        for (const auto &q : qsss[i][j]) {
          if (q.first <= X && X < q.second) {
            r = send(j);
          }
        }
      }
      assert(~r);
    } else {
      r = receive();
    }
    // truth -> truth
    pss[0].insert(pss[0].end(), qsss[0][r].begin(), qsss[0][r].end());
    // truth -> lie
    pss[1].insert(pss[1].end(), qsss[0][r ^ 1].begin(), qsss[0][r ^ 1].end());
    // lie -> truth
    pss[0].insert(pss[0].end(), qsss[1][r].begin(), qsss[1][r].end());
  }
  
  vector<int> xs;
  for (int i = 0; i < 2; ++i) {
    for (const auto &p : pss[i]) {
      for (int x = p.first; x < p.second; ++x) {
        xs.push_back(x);
      }
    }
  }
  if (xs.size() == 1) {
    return make_pair(xs[0], xs[0]);
  } else if (xs.size() == 2) {
    return make_pair(xs[0], xs[1]);
  } else if (xs.size() == 3) {
    if (~X) {
      constexpr int STRA = 215;
      const int k = find(xs.begin(), xs.end(), X) - xs.begin();
      assert(k < 3);
      int u = 0;
      for (int e = 0; e < 3; ++e) {
        const int s = STRA >> (6 * k + u) & 1;
        const int t = send(s);
        u = (s != t) ? (2 * u + 2) : (2 * u + 1);
      }
      return make_pair(-1, -1);
    } else {
      constexpr int EX[8] = {0, 0, 1, 1, 0, 1, 2, 2};
      int key = 0;
      for (int e = 0; e < 3; ++e) {
        (key <<= 1) |= receive();
      }
      const int k1 = (EX[key] + 1) % 3;
      const int k2 = (EX[key] + 2) % 3;
      return make_pair(xs[k1], xs[k2]);
    }
  } else {
    assert(false);
  }
}

void encode(int N, int X) {
  solve(N, X);
}

std::pair<int, int> decode(int N) {
  return solve(N, -1);
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 1ms

memory: 4120kb

Overall Time Limit: 500ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #2:

score: 15

Accepted

time: 1ms

memory: 4120kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #3:

score: 15

Accepted

time: 1ms

memory: 3852kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Test #4:

score: 15

Accepted

time: 1ms

memory: 3904kb

Overall Time Limit: 500ms

input:

output:

input:

output:

result:

points 1.0

Test #5:

score: 15

Accepted

time: 2ms

memory: 4120kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #6:

score: 15

Accepted

time: 1ms

memory: 4084kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #7:

score: 15

Accepted

time: 1ms

memory: 3900kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Subtask #2:

score: 85

Accepted

Test #8:

score: 85

Accepted

time: 18ms

memory: 3836kb

Overall Time Limit: 2210ms

input:

output:

input:

output:

result:

points 1.0

Test #9:

score: 85

Accepted

time: 24ms

memory: 4116kb

Overall Time Limit: 2955ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #10:

score: 85

Accepted

time: 23ms

memory: 4120kb

Overall Time Limit: 2020ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #11:

score: 85

Accepted

time: 7ms

memory: 3904kb

Overall Time Limit: 1235ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #12:

score: 85

Accepted

time: 33ms

memory: 4036kb

Overall Time Limit: 2500ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #13:

score: 85

Accepted

time: 22ms

memory: 4112kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #14:

score: 85

Accepted

time: 27ms

memory: 4112kb

Overall Time Limit: 2955ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #15:

score: 85

Accepted

time: 22ms

memory: 3856kb

Overall Time Limit: 2960ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #16:

score: 85

Accepted

time: 8ms

memory: 4084kb

Overall Time Limit: 1210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #17:

score: 85

Accepted

time: 8ms

memory: 3824kb

Overall Time Limit: 1050ms

input:

output:

input:

output:

result:

points 1.0

Test #18:

score: 85

Accepted

time: 14ms

memory: 3820kb

Overall Time Limit: 2300ms

input:

output:

input:

output:

result:

points 1.0

Test #19:

score: 85

Accepted

time: 10ms

memory: 4116kb

Overall Time Limit: 1255ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #20:

score: 85

Accepted

time: 10ms

memory: 4116kb

Overall Time Limit: 1250ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #21:

score: 85

Accepted

time: 0ms

memory: 3884kb

Overall Time Limit: 250ms

input:

output:

input:

output:

510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
167 42 1183
510
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
410
167 42 1183
510
...

result:

points 1.0

Test #22:

score: 85

Accepted

time: 12ms

memory: 4052kb

Overall Time Limit: 1230ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #23:

score: 85

Accepted

time: 14ms

memory: 4116kb

Overall Time Limit: 3210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #24:

score: 85

Accepted

time: 8ms

memory: 3856kb

Overall Time Limit: 1300ms

input:

output:

input:

output:

result:

points 1.0

Test #25:

score: 85

Accepted

time: 38ms

memory: 4084kb

Overall Time Limit: 4995ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #26:

score: 85

Accepted

time: 12ms

memory: 4116kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #27:

score: 85

Accepted

time: 12ms

memory: 3832kb

Overall Time Limit: 1220ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #28:

score: 85

Accepted

time: 24ms

memory: 3860kb

Overall Time Limit: 1710ms

input:

output:

input:

output:

result:

points 1.0

Test #29:

score: 85

Accepted

time: 23ms

memory: 4116kb

Overall Time Limit: 2355ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #30:

score: 85

Accepted

time: 19ms

memory: 4112kb

Overall Time Limit: 2960ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #31:

score: 85

Accepted

time: 14ms

memory: 4116kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0