QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#877856 | #7322. Random Numbers | Rong7 | AC ✓ | 1090ms | 90516kb | C++14 | 2.3kb | 2025-02-01 11:16:19 | 2025-02-01 11:16:19 |
Judging History
answer
// Go in my style.
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
clock_t sttime;
#define STCLOCK sttime = clock();
#define TIMENOW fprintf(stderr, "\nNOW TIME COSSEMED: %0.4lf\n", 1.0 * (clock() - sttime) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))
#define int __int128
namespace io {
int pos;
inline int read(int &p = pos) {
static bool v; static char c;
p = 0, v = false, c = getchar();
while (! isdigit(c)) {
if (c == '-') v = true;
c = getchar();
}
while (isdigit(c)) {
p = (p << 1) + (p << 3) + (c - 48);
c = getchar();
}
return p = v ? - p : p;
}
inline void write(int x) {
static int sta[65], top; top = 0;
if (x < 0) putchar('-'), x = - x;
do sta[++ top] = x % 10, x /= 10;
while (x);
while (top) putchar(sta[top --] + 48);
}
}
const int N = 2e5;
int n, m, k, a[N + 5], b[N + 5], c[N + 5], s;
pair<int, int> exg(int a, int b) {
if (!a) return {0, 1};
if (!b) return {1, 0};
auto res = exg(b, a % b);
return {res.second, res.first - a / b * res.second};
}
map<int, int> mp;
inline bool Check(int m, int k) {
for (int i = 1, w; i <= n; ++ i) {
w = (a[i] + k) % m;
if (!mp[w]) {
for (int j = 1; j < i; ++ j) ++ mp[(a[j] + k) % m];
return false;
}
-- mp[w];
}
for (int i = 1; i <= n; ++ i) ++ mp[(a[i] + k) % m];
return true;
}
signed main() {
STCLOCK
io::read(n);
for (int i = 1; i <= n; ++ i) s -= io::read(a[i]);
for (int i = 1; i <= n; ++ i) s += io::read(b[i]), ++ mp[b[i]];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (m = b[n] + 1; ; ++ m) {
int g = __gcd(n, m);
if (s % g != 0) continue;
int rnd = m / g; k = exg(n, m).first % rnd;
k = (k * (s / g) % rnd + rnd) % rnd;
while (k < m) {
if (Check(m, k)) {
io::write(m), putchar(' ');
io::write(k), putchar('\n');
TIMENOW
return 0;
}
k += rnd;
}
}
puts("NO FOUND!");
TIMENOW
return 1;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 529ms
memory: 10068kb
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: 383ms
memory: 28180kb
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: 1090ms
memory: 89232kb
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: 178ms
memory: 15232kb
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: 209ms
memory: 17368kb
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: 1087ms
memory: 90516kb
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: 37ms
memory: 10068kb
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: 30ms
memory: 10072kb
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: 34ms
memory: 10364kb
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: 173ms
memory: 19760kb
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: 346ms
memory: 26592kb
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: 315ms
memory: 27604kb
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: 109ms
memory: 12148kb
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: 242ms
memory: 20044kb
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: 283ms
memory: 22980kb
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: 250ms
memory: 23344kb
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: 312ms
memory: 25372kb
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: 258ms
memory: 23760kb
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: 322ms
memory: 26952kb
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: 401ms
memory: 29200kb
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