QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628523#7723. Hash ServerList0 0ms0kbC++206.0kb2024-10-10 20:45:292024-10-10 20:49:22

Judging History

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

  • [2024-10-10 20:49:22]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-10-10 20:45:29]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
#define debug(x) log("  >> %s: %lld\n", #x, x)
using namespace std;
using ll = long long;
using lll = __int128;
using lf = long double;
using ull = unsigned long long;

const int n = 10;
const ll mod = 141167095653376;
int T, low[n][n][n], high[n][n];
mt19937 rng(20040129);

ll norm(ll x) {
  x %= mod;
  return x < 0 ? x + mod : x;
}

ll power(ll a, ll b) {
  lll s = 1;
  for (; b; b >>= 1, a = (lll)a * a % mod)
    if (b & 1) s = (lll)s * a % mod;
  return s;
}

ll encode(                                                      //
    string s,                                                   //
    int x = 73,                                                 //
    array<int, n> a = {71, 67, 61, 59, 53, 47, 43, 41, 37, 31}, //
    array<int, n> k = {29, 23, 19, 17, 13, 11, 7, 5, 3, 2}      //
) {
  ll res = 0;
  for (int i = 0; i < n; i++) {
    int c = s[i] - 'a' + 1;
    res = (res + (lll)c * power(x, k[i]) % mod * (a[i] + c)) % mod;
  }
  return res;
}

ll s2i(string s) {
  ll res = 0;
  for (int i = 0; i < n; i++) {
    res = (res * 26 + (s[i] - 'a'));
  }
  assert(0 <= res && res < mod);
  return res;
}

string i2s(ll x) {
  string s;
  s.resize(n);
  for (int i = n - 1; i >= 0; i--) {
    s[i] = x % 26 + 'a';
    x /= 26;
  }
  assert(x == 0);
  return s;
}

namespace prog1 {
void solve() {
  for (int i = 0; i < n; i++) {   // 第几位 decoder
    for (int j = 0; j < n; j++) { // 第几个数
      string s;
      s.resize(n);
      for (int k = 0; k < n; k++) {
        if (k < i) {
          s[k] = low[i][j][k];
        } else if (k == i) {
          s[k] = j;
        } else {
          s[k] = high[i][k];
        }
        s[k] += 'a';
      }
      cout << s << endl;
      cerr << i2s(encode(s)) << endl;
    }
  }
  cout << "done" << endl;
}
} // namespace prog1

namespace prog2 {
vector<ll> rem;

struct atom {
  int x;
  ll p, q;
  ll diff[n], fun[n];

  ll get(int i) { return ((lll)i * p + (lll)i * i * q) % mod; }

  void solve(int);
} b[n];

#define thatone (rem[i] == 85569017343074 && rem[j] == 109256991037158 && rem[k] == 8496613312874)

void atom::solve( //
    int bit       // 当前处理的是第几位的hasher
) {
  for (int i = 0; i < n; i++) {     // 第几个数
    for (int j = 0; j < bit; j++) { // 第几位 (low)
      diff[i] += b[j].get(low[bit][i][j] + 1);
      // log("i=%d j=%d >> %d\n", i, j, low[bit][i][j] + 1);
    }
    diff[i] = norm(diff[i]);
  }
  // log("diff[%d] = ", bit);
  // for (int i = 0; i < n; i++) log("%lld%c", diff[i], " \n"[i + 1 == n]);

  sort(rem.begin(), rem.end());
  int len = sz(rem);
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len; j++) {
      if (i == j) continue;
      for (int k = 0; k < len; k++) {
        if (i == k || j == k) continue;
        // if (thatone) log("! i=%d j=%d k=%d\n", i, j, k);

        ll C_p_q = norm(rem[i] - diff[0]);
        ll p_q3 = norm((rem[j] - diff[1]) - (rem[i] - diff[0]));
        ll p_q5 = norm((rem[k] - diff[2]) - (rem[j] - diff[1]));
        ll q2 = norm(p_q5 - p_q3);
        if (q2 % 2 == 1) continue;
        for (int _ = 0; _ < 2; _++) {
          if (thatone) log("!!! _=%d\n", _);
          this->q = norm(q2 / 2 + _ * (mod >> 1));
          this->p = norm(p_q3 - q * 3);
          ll C = norm(C_p_q - p - q);
          if (thatone) {
            debug(C_p_q);
            debug(p_q3);
            debug(p_q5);
            debug(q2);
            debug(q);
            debug(p);
            debug(C);
          }
          bool fl = true;
          if (thatone) log("rem: %lld %lld %lld\n", rem[i], rem[j], rem[k]);
          for (int t = 0; t < n; t++) {
            fun[t] = norm(diff[t] + C + p * (t + 1) + q * (t + 1) * (t + 1));
            if (thatone) debug(fun[t]);
            if (t > 2) {
              auto it = lower_bound(all(rem), fun[t]);
              if (it == rem.end() || *it != fun[t]) {
                fl = false;
                break;
              }
            }
          }
          if (fl) {
            assert(fun[0] == rem[i]);
            assert(fun[1] == rem[j]);
            assert(fun[2] == rem[k]);
            for (int t = 0; t < n; t++) {
              rem.erase(lower_bound(all(rem), fun[t]));
            }
            log("FOUND bit=%d >> p=%lld q=%lld\n", bit, p, q);
            return;
          }
        }
      }
    }
  }
  log("bit[%d] failed!\n", bit);
  assert(false);
}

ll myencode(string s) {
  ll res = 0;
  for (int i = 0; i < n; i++) {
    res += b[i].get(s[i] - 'a' + 1);
  }
  return res % mod;
}

void solve() {
  int _;
  cin >> _;
  assert(_ == n * n);
  for (int i = 0; i < n * n; i++) {
    string s;
    cin >> s;
    rem.push_back(s2i(s));
    // log("i=%d s=%s x=%lld\n", i, s.c_str(), s2i(s));
  }
  for (int i = 0; i < n; i++) {
    b[i].solve(i);
  }

  for (int i = 1; i <= n * n; i++) {
    string s;
    cin >> s;
    assert(s.length() == n);
    cout << i2s(myencode(s)) << endl;
  }
}
} // namespace prog2

int main() {
#ifdef memset0
  freopen("H.in", "r", stdin);
  // freopen("H.out", "w", stdout);
#endif
  cin.tie(0)->sync_with_stdio(0);
  // cout << encode("aaaaaaaaaa") << endl;
  // cout << i2s(encode("aaaaaaaaaa")) << endl;
  // return 0;

  cin >> T;
  for (int i = 0; i < n; i++) {     // 第几位 decoder
    for (int j = 0; j < n; j++) {   // 第几个数
      for (int k = 0; k < i; k++) { // 第几位的数码
        low[i][j][k] = rng() % 26;
      }
    }
  }
  for (int i = 0; i < n; i++) {       // 第几位 decoder
    for (int k = i + 1; k < n; k++) { // 第几位的数码
      high[i][k] = rng() % 26;
    }
  }
  if (T == 1) {
    prog1::solve();
  } else if (T == 2) {
    prog2::solve();
  }
}

详细

Test #1:

score: 0
Instance #1 Time Limit Exceeded

input:

1
ndfhrzmmlq
dbtusidgtk
tlnputvfcu
kgmsziohnu
bmregaioak
teaxovdyoq
lgpyztanem
dukimtyfvy
wtkabxxcpa
qdoztexdjs
ptttxbxies
udfaxiqglq
borwqicyvy
bozegnbfag
auktitljge
vefnyoyqre
fnucuohotu
rggcxcuzry
hlxazgynem
jbweawrale
vhmlrkjnym
vkzmtmacnw
bhzrczyfrk
yayrylktpo
gopjybgmze
uquulirdzi
jkrqoapblu
a...

output:

ahzvaqhdff
bhzvaqhdff
chzvaqhdff
dhzvaqhdff
ehzvaqhdff
fhzvaqhdff
ghzvaqhdff
hhzvaqhdff
ihzvaqhdff
jhzvaqhdff
gazcyylaig
ybzcyylaig
eczcyylaig
zdzcyylaig
qezcyylaig
dfzcyylaig
igzcyylaig
rhzcyylaig
pizcyylaig
ujzcyylaig
waacpwnpiu
tcbcpwnpiu
gsccpwnpiu
tydcpwnpiu
hxecpwnpiu
vsfcpwnpiu
hvgcpwnpiu
hgh...

input:

2
100
vhmlrkjnym
qlyffbuutu
bhzrczyfrk
lqcpwxefhq
wscdwkluos
ecuuijrrwk
wtkabxxcpa
cvzlhdiplm
jbweawrale
udcxpoulns
hqqjujhmfg
mucgklfkyg
auktitljge
myngxvuoku
gtnxszwrxq
mrcbgmgmto
hxlcuddnqo
tlnputvfcu
adnbhvonau
xrhcepnibg
dkrnywyjdk
thtmvwgmuc
aihbjugisa
tirwcpehqu
jzunixvmwm
rvwsbyrxls
lgpyztan...

output:


result: