QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#715087 | #7322. Random Numbers | hos_lyric | AC ✓ | 136ms | 43432kb | C++14 | 4.4kb | 2024-11-06 10:23:15 | 2024-11-06 10:23:15 |
Judging History
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,我给组数据试试?
详细
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