QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#874738	#4208. Flight to the Ford	duongnc000	100 ✓	64ms	3968kb	C++20	3.8kb	2025-01-28 14:48:08	2025-01-28 14:48:10

Judging History

This is the latest submission verdict.

[2025-01-28 14:48:10]
Judged

Verdict: 100
Time: 64ms
Memory: 3968kb

Show

[2025-01-28 14:48:08]
Submitted

answer

#include"communication.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

vector<int> vec = {0, 6, 9, 15};
vector<int> fib = {0, 1, 2, 4, 5, 8, 9, 10};
vector<array<int, 2>> dev = {{0, 2}, {0, 2}, {0, 1}, {1, 2}, {0, 1}, {0, 3}, {1, 3}, {1, 3}, {0, 2}, {0, 2}, {0, 3}, {2, 3}, {1, 2}, {2, 3}, {1, 3}, {1, 3}};

vector<pair<int, deque<array<int, 2>>>> split(int len, deque<array<int, 2>> dq) {
  int cur = len / 2, r = len % 2;
  vector<pair<int, deque<array<int, 2>>>> ans;
  for (int i = 0; i < 2; ++i) {
    int nlen = cur + (i < r), clen = 0;
    deque<array<int, 2>> vec;
    while (clen < nlen) {
      auto [l, r] = dq.front(); dq.pop_front();
      if (clen + r - l >= nlen) {
        int nr = l + nlen - clen;
        if (nr < r) dq.push_front({nr, r});
        vec.push_back({l, nr});
        clen = nlen;
      }
      else {
        vec.push_back({l, r});
        clen += r - l;
      }
    }
    ans.push_back({nlen, vec});
  }
  return ans;
}

pair<int, deque<array<int, 2>>> merge(pair<int, deque<array<int, 2>>> A, pair<int, deque<array<int, 2>>> B) {
  deque<array<int, 2>> res;
  res.insert(res.end(), all(A.second));
  res.insert(res.end(), all(B.second));
  return {A.first + B.first, res};
}

bool check(int val, deque<array<int, 2>> &dq) {
  for (auto &[l, r] : dq) if (l <= val and val < r) return true;
  return false;
}

int get_index(int pos, vector<pair<int, deque<array<int, 2>>>> &vec) {
  for (int i = 0; i < isz(vec); ++i) {
    int l = vec[i].second.front()[0];
    int r = vec[i].second.back()[1];
    if (l <= pos and pos < r) return i;
  }
  assert(0);
  return -1;
}

array<int, 2> get_two(const deque<array<int, 2>> &dq) {
  int len = 0;
  for (auto [l, r] : dq) {
    len += r - l;
  }
  if (len == 1) {
    return {dq[0][0], dq[0][0]};
  }
  assert(len == 2);
  if (isz(dq) == 2) return {dq[0][0], dq[1][0]};
  return {dq[0][0], dq[0][0] + 1};
}

void encode(int N, int X) {
  --X;
  int lenC = N, lenW = 0, step = 0;
  deque<array<int, 2>> dqC = {{0, N}}, dqW = {};
  while (lenC + lenW > 4) {
    auto nC = split(lenC, dqC);
    auto nW = split(lenW, dqW);
    auto U = merge(nC[0], nW[1]);
    auto bit = send(check(X, U.second));
    if (bit) {
      tie(lenC, dqC) = U; // X is inside of U
      tie(lenW, dqW) = nC[1]; // X is not insed of U
    }
    else {
      tie(lenC, dqC) = merge(nC[1], nW[0]); // X is not inside of U
      tie(lenW, dqW) = nC[0]; // X is inside of U
    }
    ++step;
  }
  assert(step <= 96);
  vector<int> cand;
  for (auto [l, r] : dqC) for (int i = l; i < r; ++i) cand.push_back(i);
  for (auto [l, r] : dqW) for (int i = l; i < r; ++i) cand.push_back(i);
  for (int i = 0; i < isz(cand); ++i) if (cand[i] == X) {
    for (int bit = 3; bit >= 0; --bit) send(vec[i] >> bit & 1);
    return;
  }
}

pair<int, int> decode(int N) {
  int lenC = N, lenW = 0;
  deque<array<int, 2>> dqC = {{0, N}}, dqW = {};
  while (lenC + lenW > 4) {
    auto nC = split(lenC, dqC);
    auto nW = split(lenW, dqW);
    auto U = merge(nC[0], nW[1]);
    auto bit = receive();
    if (bit) {
      tie(lenC, dqC) = U; // X is inside of U
      tie(lenW, dqW) = nC[1]; // X is not insed of U
    }
    else {
      tie(lenC, dqC) = merge(nC[1], nW[0]); // X is not inside of U
      tie(lenW, dqW) = nC[0]; // X is inside of U
    }
  }
  vector<int> cand;
  for (auto [l, r] : dqC) for (int i = l; i < r; ++i) cand.push_back(i);
  for (auto [l, r] : dqW) for (int i = l; i < r; ++i) cand.push_back(i);
  int idx = 0;
  for (int i = 0; i < 4; ++i) {
    idx = idx << 1 | (int)receive();
  }
  auto [x, y] = dev[idx];
  if (y >= isz(vec)) y = x;
  return {cand[x] + 1, cand[y] + 1};
}

源文件, 语言: C++20

详细

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 1ms

memory: 3840kb

Overall Time Limit: 500ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #2:

score: 15

Accepted

time: 0ms

memory: 3840kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #3:

score: 15

Accepted

time: 0ms

memory: 3840kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Test #4:

score: 15

Accepted

time: 2ms

memory: 3840kb

Overall Time Limit: 500ms

input:

output:

input:

output:

result:

points 1.0

Test #5:

score: 15

Accepted

time: 2ms

memory: 3968kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #6:

score: 15

Accepted

time: 0ms

memory: 3968kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #7:

score: 15

Accepted

time: 0ms

memory: 3840kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Subtask #2:

score: 85

Accepted

Test #8:

score: 85

Accepted

time: 21ms

memory: 3840kb

Overall Time Limit: 2210ms

input:

output:

input:

output:

result:

points 1.0

Test #9:

score: 85

Accepted

time: 47ms

memory: 3840kb

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: 30ms

memory: 3840kb

Overall Time Limit: 2020ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #11:

score: 85

Accepted

time: 21ms

memory: 3840kb

Overall Time Limit: 1235ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #12:

score: 85

Accepted

time: 35ms

memory: 3840kb

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: 39ms

memory: 3840kb

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: 48ms

memory: 3968kb

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: 36ms

memory: 3840kb

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: 24ms

memory: 3840kb

Overall Time Limit: 1210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #17:

score: 85

Accepted

time: 19ms

memory: 3840kb

Overall Time Limit: 1050ms

input:

output:

input:

output:

result:

points 1.0

Test #18:

score: 85

Accepted

time: 27ms

memory: 3840kb

Overall Time Limit: 2300ms

input:

output:

input:

output:

result:

points 1.0

Test #19:

score: 85

Accepted

time: 17ms

memory: 3840kb

Overall Time Limit: 1255ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #20:

score: 85

Accepted

time: 20ms

memory: 3840kb

Overall Time Limit: 1250ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #21:

score: 85

Accepted

time: 4ms

memory: 3840kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #22:

score: 85

Accepted

time: 27ms

memory: 3968kb

Overall Time Limit: 1230ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #23:

score: 85

Accepted

time: 37ms

memory: 3840kb

Overall Time Limit: 3210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #24:

score: 85

Accepted

time: 20ms

memory: 3840kb

Overall Time Limit: 1300ms

input:

output:

input:

output:

result:

points 1.0

Test #25:

score: 85

Accepted

time: 64ms

memory: 3840kb

Overall Time Limit: 4995ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #26:

score: 85

Accepted

time: 27ms

memory: 3840kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #27:

score: 85

Accepted

time: 19ms

memory: 3840kb

Overall Time Limit: 1220ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #28:

score: 85

Accepted

time: 20ms

memory: 3840kb

Overall Time Limit: 1710ms

input:

output:

input:

output:

result:

points 1.0

Test #29:

score: 85

Accepted

time: 37ms

memory: 3840kb

Overall Time Limit: 2355ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #30:

score: 85

Accepted

time: 38ms

memory: 3840kb

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: 44ms

memory: 3968kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0