QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119607#6669. Mapahos_lyric#0 3ms4068kbC++145.2kb2023-07-05 12:50:182024-07-04 00:18:08

Judging History

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

  • [2024-07-04 00:18:08]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:4068kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 12:50:18]
  • 提交

answer

#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 <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; }


int mix(int x) {
  x = (20230705LL * x) % 1'000'000'403;
  return x;
}

constexpr int E = 30;
constexpr int F = 10;
constexpr int GP = 9;
constexpr int GM = 8;
constexpr int M0 = 150;

string toBinary(int len, int x) {
  string s(len, '?');
  for (int e = 0; e < len; ++e) s[e] = "01"[x >> e & 1];
  return s;
}
int fromBinary(const string &s) {
  const int len = s.size();
  int x = 0;
  for (int e = 0; e < len; ++e) x |= (s[e] - '0') << e;
  return x;
}

string encode(int N, const vector<int> &X, const vector<int> &Y) {
  string S;
  
  int P;
  vector<int> H(N);
  for (int a = 0; a < 1 << GP; ++a) {
    P = (1 << F) - 1 - a;
    for (int i = 0; i < N; ++i) {
      H[i] = mix(X[i]) % P;
    }
    if ((int)set<int>(H.begin(), H.end()).size() == N) {
cerr<<"perfect a = "<<a<<", P = "<<P<<endl;
      S += toBinary(GP, a);
      goto foundPerfect;
    }
  }
  assert(false);
 foundPerfect:{}
  
  int minCost = 1001001001;
  int am = -1;
  for (int a = 0; a < 1 << GM; ++a) {
    const int M = M0 + a;
    vector<int> freq(M);
    for (int i = 0; i < N; ++i) {
      ++freq[H[i] % M];
    }
    int cost = M;
    for (int m = 0; m < M; ++m) {
      cost += F * max(freq[m] - 1, 0);
    }
cerr<<"M = "<<M<<": cost = "<<cost<<endl;
    if (chmin(minCost, cost)) {
      am = a;
    }
  }
  const int M = M0 + am;
  S += toBinary(GM, am);
  
  vector<vector<pair<int, int>>> hiss(M);
  for (int i = 0; i < N; ++i) {
    hiss[H[i] % M].emplace_back(H[i], i);
  }
  for (int m = 0; m < M; ++m) {
    auto &his = hiss[m];
    sort(his.begin(), his.end());
  }
// cerr<<"hiss = "<<hiss<<endl;
  for (int m = 0; m < M; ++m) {
    const auto &his = hiss[m];
    for (const auto &hi : his) {
      const int i = hi.second;
      S += toBinary(E, Y[i]);
    }
  }
  for (int m = 0; m < M; ++m) {
    const auto &his = hiss[m];
    S += (!his.empty()) ? '1' : '0';
  }
  for (int m = 0; m < M; ++m) {
    const auto &his = hiss[m];
    for (int j = 1; j < (int)his.size(); ++j) {
      S += toBinary(F, his[j].first);
    }
  }
  return S;
}

vector<int> decode(int N, int Q, int K, const string &S, const vector<int> &Z) {
  int P, M;
  map<int, int> mapa, nazo;
  {
    int cur = 0;
    P = (1 << F) - 1 - fromBinary(S.substr(cur, GP)); cur += GP;
    const int am = fromBinary(S.substr(cur, GM)); cur += GM;
    M = M0 + am;
    vector<int> Y(N);
    for (int i = 0; i < N; ++i) {
      Y[i] = fromBinary(S.substr(cur, E)); cur += E;
    }
    vector<vector<int>> hss(M);
    for (int m = 0; m < M; ++m) {
      const char any = S[cur++];
      if (any != '0') {
        hss[m].push_back(-1);
      }
    }
    for (; cur < K; ) {
      const int h = fromBinary(S.substr(cur, F)); cur += F;
      hss[h % M].push_back(h);
    }
// cerr<<"hss = "<<hss<<endl;
    {
      int i = 0;
      for (int m = 0; m < M; ++m) {
        for (const int h : hss[m]) {
          const int y = Y[i++];
          if (~h) {
            mapa[h] = y;
          } else {
            nazo[m] = y;
          }
        }
      }
    }
    assert(cur == K);
  }
  vector<int> ans(Q);
  for (int q = 0; q < Q; ++q) {
    const int h = mix(Z[q]) % P;
    auto it = mapa.find(h);
    if (it != mapa.end()) {
      ans[q] = it->second;
    } else {
      ans[q] = nazo[h % M];
    }
  }
  return ans;
}

int main() {
  int T;
  scanf("%d", &T);
  if (T == 1) {
    int N;
    scanf("%d", &N);
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d%d", &X[i], &Y[i]);
    }
    const string S = encode(N, X, Y);
    const int K = S.size();
    printf("%d\n", K);
    puts(S.c_str());
  } else {
    int N, Q, K;
    scanf("%d%d%d", &N, &Q, &K);
    char buf[6010];
    scanf("%s", buf);
    const string S = buf;
    vector<int> Z(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &Z[q]);
    }
    const auto ans = decode(N, Q, K, S, Z);
    for (int q = 0; q < Q; ++q) {
      printf("%d\n", ans[q]);
    }
  }
  return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 89.5667
Acceptable Answer
time: 3ms = 3ms + 0ms
memory: 3828kb,3748kb

input:

1
100
495528311 963488152
269613430 443544124
700489871 792354118
151890319 506569919
180452297 13229948
684464994 543841485
978085128 903812192
238355172 441140842
28061035 783291471
530823766 718942732
936853023 439421263
201361623 226633955
304644844 778868118
864860135 461524170
88300500 6959354...

output:

3313
0111010000101100000101100000001001000101101110100111011100101110101110100100100010011011011100111101011011110010100110000100000110000100100000000010111001100011110010010110001110100110100101101100111000000101000010101101100000101101011010010110001100000100000101011000111110110100110011100011110...

input:

2
100 79 3313
0111010000101100000101100000001001000101101110100111011100101110101110100100100010011011011100111101011011110010100110000100000110000100100000000010111001100011110010010110001110100110100101101100111000000101000010101101100000101101011010010110001100000100000101011000111110110100110011...

output:

310305144
821194635
174780370
903812192
805026231
996046536
439421263
645287342
90686849
20101025
440972097
543841485
176553522
249563964
461524170
348624865
848301562
506569919
306718453
206848250
382805509
278712030
964702808
868944393
493895143
39665197
574757075
441140842
785665865
229376884
551...

result:

points 0.89566666670 ok K = 3313

Test #2:

score: 89.5333
Acceptable Answer
time: 1ms = 0ms + 1ms
memory: 4068kb,3744kb

input:

1
100
743248071 842720888
367650901 130970775
297946283 705168964
771526942 537186020
245003150 707948455
643491261 668001146
311535032 293708068
183828318 18515526
593973840 915870006
102456762 64193833
729806890 839221652
47145974 35682954
668676377 228428310
370700393 569441954
250911162 48980047...

output:

3314
0100110001110101000101011111101111101011000001001111110000000110010101111100010100110001011111101001010101111001000011001111110110011011100100100100001011000000110001010011001010110000001011111000010001011111001000101010100011100101101000100001101001011110011110110001101101011110000011001101100...

input:

2
100 79 3314
0100110001110101000101011111101111101011000001001111110000000110010101111100010100110001011111101001010101111001000011001111110110011011100100100100001011000000110001010011001010110000001011111000010001011111001000101010100011100101101000100001101001011110011110110001101101011110000011...

output:

442563406
97578442
469403815
293708068
138158276
720700065
839221652
674386240
810209830
563527225
259979005
668001146
813899310
943777483
569441954
226088806
825435650
537186020
131383422
83733737
830289758
425793016
858146541
609883097
414389335
407054915
47572024
18515526
276587480
810627636
4972...

result:

points 0.89533333330 ok K = 3314

Test #3:

score: 0
Runtime Error

input:

1
100
770174568 168127255
893508708 185778664
976425263 477317099
287595878 512153851
621600374 418802856
818787535 612197605
796811122 566496677
789841517 873731343
43178468 619503942
597852289 471053284
66112404 635260765
158101403 199253397
680158192 123081916
626776438 29107026
721141470 5177084...

output:


result: