QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#715087#7322. Random Numbershos_lyricAC ✓136ms43432kbC++144.4kb2024-11-06 10:23:152024-11-06 10:23:15

Judging History

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

  • [2024-11-06 10:23:15]
  • 评测
  • 测评结果:AC
  • 用时:136ms
  • 内存:43432kb
  • [2024-11-06 10:23:15]
  • 提交

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 <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")


// cannot use count
// no move constructor (==> use pointer for merge tech)
// unordered_set by value: __gnu_pbds::null_type
// no erase(iterator)
#include <ext/pb_ds/assoc_container.hpp>
using __gnu_pbds::gp_hash_table;

// https://codeforces.com/blog/entry/62393
#include <chrono>
struct Hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  size_t operator()(const pair<int, int> &a) const {
    return operator()((uint64_t)a.first << 32 | a.second);
  }
};
template <class K> using Set = gp_hash_table<K, __gnu_pbds::null_type, Hash>;
template <class K, class V> using Map = gp_hash_table<K, V, Hash>;


// a x + b y = (+/-) gcd(a, b)
//   (a, 0): g = a, x = 1, y = 0
//   (0, b), (b, b), (-b, b) (b != 0): g = b, x = 0, y = 1
//   otherwise: 2 |x| <= |b|, 2 |y| <= |a|
// S: signed integer
template <class S> S gojo(S a, S b, S &x, S &y) {
  if (b != 0) {
    const S g = gojo(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
  } else {
    x = 1;
    y = 0;
    return a;
  }
}


pair<Int, Int> solve(int N, const vector<Int> &A, const vector<Int> &B) {
  Map<Int, int> freqB;
  auto check = [&](Int m, Int k) -> bool {
    Map<Int, int> freq;
    for (const Int a : A) {
      const Int b = (a + k) % m;
      auto it = freqB.find(b);
      if (it != freqB.end()) {
        if (++freq[b] > it->second) return false;
      } else {
        return false;
      }
    }
    return true;
  };
  
  __int128 sumA = 0;
  for (const Int a : A) {
    sumA += a;
  }
  Int sumB = 0, maxB = 0;
  for (const Int b : B) {
    sumB += b;
    chmax(maxB, b);
    ++freqB[b];
  }
  for (Int m = maxB + 1; ; ++m) {
    // sumA + N k == sumB  (mod m)
    Int x, y;
    const Int g = gojo<Int>(N, m, x, y);
    const Int m0 = m / g;
    if ((sumB - sumA) % g) continue;
    Int k0 = (__int128)x * ((sumB - sumA) / g % m0) % m0;
    if (k0 < 0) k0 += m0;
// cerr<<"m = "<<m<<", g = "<<g<<endl;
    for (Int k = k0; k < m; k += m0) {
// assert((sumA+(__int128)N*k-sumB)%m==0);
      if (check(m, k)) {
        return make_pair(m, k);
      }
    }
  }
}

void test(int N, Int M) {
  mt19937_64 rng(58);
  const Int K = rng() % M;
  vector<Int> A(N), B(N);
  for (int i = 0; i < N; ++i) {
    A[i] = 1 + rng() % 1'000'000'000'000'000'000LL;
    B[i] = (A[i] + K) % M;
    swap(B[rng() % (i + 1)], B[i]);
  }
  const auto ans = solve(N, A, B);
  cerr << "[test] " << N << " " << M << " " << K << ": " << ans << endl;
}

int main() {
  // test(2 * 83160, 10'000'000'000LL);
  
  int N;
  for (; ~scanf("%d", &N); ) {
    vector<Int> A(N), B(N);
    for (int i = 0; i < N; ++i) scanf("%lld", &A[i]);
    for (int i = 0; i < N; ++i) scanf("%lld", &B[i]);
    const auto ans = solve(N, A, B);
    printf("%lld %lld\n", ans.first, ans.second);
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 92ms
memory: 4784kb

input:

100000
567521362129079894 696655062397105489 618592056868108007 305121979898345388 418241613626143516 566981041096909436 687040795047811890 413478956193714535 294233239559482609 517064297715474906 919243760085177084 146712184879435114 334896924897329674 808181231522418580 201231480069623536 26529430...

output:

100 67

result:

ok ok

Test #2:

score: 0
Accepted
time: 60ms
memory: 43328kb

input:

200000
279519034965658533 597593214175301180 791322407400185163 578922257802743818 414641183084379116 322797787270966916 290473958850416021 68048123764088964 295440872117700499 53885977901037256 884227817550465910 435454695330542508 543950240412210545 861061959631272210 610282134233366541 8147478322...

output:

9551360648 6883666787

result:

ok ok

Test #3:

score: 0
Accepted
time: 136ms
memory: 43284kb

input:

200000
167774018375528485 714562772221376663 198818958454505969 581190629893484837 438687470464075495 790572767580670700 710940444599804113 650871502364047098 596477567071759597 702504178760375793 74780058995621376 382060312959449666 943533333637489584 152035322602398106 387034388851610387 579808941...

output:

9000000000 8642555095

result:

ok ok

Test #4:

score: 0
Accepted
time: 45ms
memory: 15712kb

input:

200000
969355099228899258 976159949555296736 802508646465407242 46626568761849462 955314000064063902 15491291741346369 179578927212839979 175131627318252840 374434845157654471 946698014293742043 811445057322360411 567542625399944716 764486828373518528 818367334248629302 386724974673137895 1418983366...

output:

47673 40183

result:

ok ok

Test #5:

score: 0
Accepted
time: 48ms
memory: 24752kb

input:

200000
765445059246555999 681901042106328807 465864934238172274 243131593489608996 276149997589645601 746433367825608749 620179206756331460 511531805533388669 839496852746012088 381417361898824156 601853897705289402 72959549751321296 787978525457595768 352180001635392339 25956249948281189 5596732371...

output:

81616 14975

result:

ok ok

Test #6:

score: 0
Accepted
time: 121ms
memory: 43232kb

input:

200000
156282775823401969 947358889962289044 361730056390202851 168994319775016864 603322591958960142 230052223269682503 58280711634268561 292730685868042692 826494652002174982 497799510257381214 290375263361319925 477924035558677757 928677583288703117 47063250453688063 74054379791381136 32611548990...

output:

10000000000 8975759010

result:

ok ok

Test #7:

score: 0
Accepted
time: 25ms
memory: 5760kb

input:

165129
973702899375702220 60070105204808273 991689199398693629 586101349256132432 231276199578319106 459136253066951573 408712240043510152 606452600536173543 671932763978794830 236326136796867745 441073904586805499 811458740886675368 134704707106081323 508646784683683224 98060075027786186 6684037359...

output:

11 10

result:

ok ok

Test #8:

score: 0
Accepted
time: 14ms
memory: 5432kb

input:

130862
965590697645040038 474660411930491723 974713009854214853 698594145526360449 816444496530102414 86439887140984714 370278108056173265 733736485861913103 464982528067491983 596361983859067655 674854837707203258 838282186664705045 569194771883409214 631326278550178606 777837351168505924 766212263...

output:

10 0

result:

ok ok

Test #9:

score: 0
Accepted
time: 29ms
memory: 6012kb

input:

189161
391186992224766495 901787768763096589 303435328975857999 127735825734679739 887271840290435832 951291826588732654 987139524243905047 501319072181170356 193009495234568187 277097206671161012 873611585425326819 860224708080788335 294848483935974117 571243486101342920 20763518831931664 887517430...

output:

2 0

result:

ok ok

Test #10:

score: 0
Accepted
time: 32ms
memory: 23632kb

input:

120866
415492147115976892 919839236173119354 859361147208207092 262932822956522346 926689655826860283 77865212191003157 746953981834275277 22708776375878800 1106037329517299 396865412531168989 183459842368902306 535434866081256865 378064186615402789 858467183551246733 510945116493074196 564746498849...

output:

1136506277 278791342

result:

ok ok

Test #11:

score: 0
Accepted
time: 53ms
memory: 43432kb

input:

198413
684369210788621157 885609985996990513 728849710386503782 583055512411882831 212155617872852871 49420427479532288 814967112455042056 635662190270014579 210903976405227590 58804219272057751 785068257884704645 577540670987545205 636756771084300272 182753012533571289 123672873987381469 5473466804...

output:

1000000000 152615432

result:

ok ok

Test #12:

score: 0
Accepted
time: 50ms
memory: 42488kb

input:

150572
395492865023777707 977627909376610783 859996300459940256 830357048470883841 181372081453349067 333426927189717594 266490043502084542 721476607820106531 812919010807897561 534757234320001136 146179570125312187 591504061399717574 845757670439048438 844093148486511856 200295956261130241 39274820...

output:

9381465204 8188734447

result:

ok ok

Test #13:

score: 0
Accepted
time: 26ms
memory: 10608kb

input:

165701
931853977837451977 273579733469948569 915822295838388443 462442310714925280 501262858285822384 325623330499263993 229917362477428723 697536073264148580 306680057811118127 500744271067428374 783088671132104338 250634627255022056 7910013473604851 745754175890535217 567857726041429269 2134634490...

output:

17559 13852

result:

ok ok

Test #14:

score: 0
Accepted
time: 36ms
memory: 24496kb

input:

187316
911754110884643935 44378961143673195 115675978858733192 267763130331719916 633944201084670919 362731262359122809 769223318485523983 512806629344513379 793313170026084756 14662162014123691 855358581706841777 841967925219514752 437117460772943372 425398527734977797 346807647901887223 9579664420...

output:

149179 47710

result:

ok ok

Test #15:

score: 0
Accepted
time: 58ms
memory: 42988kb

input:

177741
542406326988906376 8542953564782709 382784755339027460 406208556842395104 440395578325356154 225088375763169420 21173674399624785 277673558165932437 868339690219905220 933384078186589035 442795341303157438 199631038961792798 185463019522187712 431800196463991259 720181865275778823 54240228961...

output:

1330588 108454

result:

ok ok

Test #16:

score: 0
Accepted
time: 47ms
memory: 42536kb

input:

160373
407329277280716003 747357751165840343 245984040037938773 587700121980815826 351299837679281708 24398240658097488 305930243029629324 634758313477079669 387624908109785657 389988603239191997 446931390693826012 162581288660180441 296151063632814985 504488036510910399 751162179062675967 889985277...

output:

19907227 3711950

result:

ok ok

Test #17:

score: 0
Accepted
time: 50ms
memory: 43132kb

input:

179254
910454388577505698 72344997023218583 433239688888186148 998003603297315524 530618229278125776 791204208066457709 330888746423214100 633457499828896217 712079112143228387 330921627382675885 565744612824230144 492750871031587798 254383906992526972 709328463450809260 987365873170070653 818474445...

output:

188861778 157748613

result:

ok ok

Test #18:

score: 0
Accepted
time: 47ms
memory: 42448kb

input:

153014
918632685073065095 382020103044347182 276194176793782731 425561801741581894 388637533671390983 458812183712637850 214185521305443342 915710672227122692 629814527509035271 787439242980144761 693256802359044484 502678716967473053 447232811742668588 912379462362599869 971933545789205340 13841741...

output:

1196540029 1033033258

result:

ok ok

Test #19:

score: 0
Accepted
time: 50ms
memory: 43088kb

input:

176588
943157584552449011 168880745466033183 185379842486884988 271100660572071503 23625479900963011 772075836921357269 36806152455334313 367895570687287113 290796281462513953 54549860101792937 706744024223535654 336292910569308778 99055597204752367 347428765792186320 424354120408321633 985251880534...

output:

10000000000 9846457408

result:

ok ok

Test #20:

score: 0
Accepted
time: 56ms
memory: 43420kb

input:

200000
515174294040396153 740304040584436914 909808728637312370 885165457538604704 44074006022918666 814303722321661441 378576852477731030 379104642560824621 859088412548400726 754803070142122319 535202718129848030 764421919225843242 600089223223639845 192574979539203410 20300899802272435 3454904375...

output:

9967792537 5770859548

result:

ok ok

Extra Test:

score: 0
Extra Test Passed