QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790121 | #9804. Guess the Polygon | xhytom | AC ✓ | 8ms | 4020kb | C++23 | 4.7kb | 2024-11-28 01:37:33 | 2024-11-30 11:51:00 |
Judging History
answer
/*
_/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/_/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/ _/_/
_/_/ _/_/_/_/_/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/_/ _/ _/
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using i64 = long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define multi int _;cin>>_;while(_--)
#define int long long
#define pb push_back
#define eb emplace_back
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
mt19937_64 mrand(chrono::steady_clock().now().time_since_epoch().count());
int rnd(int l,int r){ return mrand() % (r - l + 1) + l;}
#ifdef localfreopen
#define debug(x) cerr << #x << " = " << (x) << endl;
void test() {cerr << "\n";}
template<typename T, typename... Args>
void test(T x, Args... args) {cerr << x << " ";test(args...);}
#else
#define debug //
#define test //
#endif
const ll MOD = 998244353;
// const ll MOD = 1e9+7;
ll ksm(ll x,ll y){ll ans=1;x%=MOD;while(y){if(y&1)ans=ans*x%MOD;x=x*x%MOD,y/=2;}return ans;}
const int P1 = 972152273, base1 = 809;
const int P2 = 905563261, base2 = 919;
const ll N = 200005;
//head
void solve() {
int n;
std::cin >> n;
std::vector<int> q;
std::map<int, int> cnt;
for (int i = 1; i <= n; i++) {
int x, y;
std::cin >> x >> y;
q.push_back(x);
cnt[x]++;
}
std::sort(q.begin(), q.end());
q.erase(std::unique(q.begin(), q.end()), q.end());
long double ans = 0;
std::map<int, long double> left, right, mid;
if (cnt[q[0]] == 1) mid[q[0]] = 0;
else {
int x = q[0];
std::cout << "? " << x << " 1" << std::endl;
long double a, b;
std::cin >> a >> b;
a = a / b;
mid[x] = a;
}
if (cnt[q.back()] == 1) mid[q.back()] = 0;
else {
int x = q.back();
std::cout << "? " << x << " 1" << std::endl;
long double a, b;
std::cin >> a >> b;
a = a / b;
mid[x] = a;
}
for (int i = 1; i < q.size() - 1; i++) {
int x = q[i];
if (cnt[x] == 1) {
std::cout << "? " << x << " 1" << std::endl;
long double a, b;
std::cin >> a >> b;
a = a / b;
mid[x] = a;
} else {
long double a, b;
std::cout << "? " << x * 4 - 1 << " 4" << std::endl;
std::cin >> a >> b;
a = a / b;
left[x] = a;
std::cout << "? " << x * 4 + 1 << " 4" << std::endl;
std::cin >> a >> b;
a = a / b;
right[x] = a;
}
}
for (int i = 1; i < q.size(); i++) {
int lx = q[i - 1], rx = q[i];
if (mid.count(lx) && mid.count(rx)) {
long double len1 = mid[lx], len2 = mid[rx];
ans += (len1 + len2) * (rx - lx);
// test("MM", len1, len2, lx, rx);
} else if (right.count(lx) && mid.count(rx)) {
long double len1 = right[lx], len2 = mid[rx];
long double dx = (len2 - len1) / (rx - lx - 0.25);
len1 -= dx / 4;
ans += (len1 + len2) * (rx - lx);
// test("RM", len1, len2, lx, rx);
} else if (mid.count(lx) && left.count(rx)) {
long double len1 = mid[lx], len2 = left[rx];
long double dx = (len2 - len1) / (rx - lx - 0.25);
len2 += dx / 4;
ans += (len1 + len2) * (rx - lx);
// test("ML", len1, len2, lx, rx);
} else if (right.count(lx) && left.count(rx)) {
long double len1 = right[lx], len2 = left[rx];
ans += (len1 + len2) * (rx - lx);
// test("RL", len1, len2, lx, rx);
}
// test(lx, rx);
debug(ans);
}
int res = (int)(ans + 0.0001);
if (res % 2 == 0) {
std::cout << "! " << res / 2 << " 1" << std::endl;
} else {
std::cout << "! " << res << " 2" << std::endl;
}
}
signed main()
{
#ifdef localfreopen
// freopen("1.in","r",stdin);
#endif
fastio
std::cout << std::fixed << std::setprecision(10);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
input:
2 4 3 0 1 3 1 1 0 0 3 2 7 4 3 0 0 999 1000 1000 999 1999 1000
output:
? 3 4 ? 5 4 ! 3 1 ? 999 1 ! 1999 2
result:
ok correct! (2 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
9 4 1 1 1 3 3 0 0 0 9 4 7 8 4 0 0 1 3 1 1 3 0 3 4 21 8 4 0 0 3 0 1 2 1 1 3 4 7 8 4 0 0 3 0 1 2 1 1 3 2 7 8 4 0 0 3 0 1 1 1 2 3 4 7 4 3 1000 0 0 0 0 1000 1000 1 4 0 0 1000 0 1000 1000 0 1000 1000 1 1000 1 5 0 1 1000 1000 1000 0 0 1000 1 0 999 1 1000 1 1000 1 9 4 1000 3 1 2 1000 3 1000 1 1 2 1 0 0 1 1...
output:
? 3 4 ? 5 4 ! 5 2 ? 3 4 ? 5 4 ! 7 2 ? 3 4 ? 5 4 ! 3 2 ? 3 4 ? 5 4 ! 2 1 ? 3 4 ? 5 4 ! 5 2 ? 0 1 ! 500000 1 ? 0 1 ? 1000 1 ! 1000000 1 ? 0 1 ? 1000 1 ? 1 1 ! 1999999 2 ? 4 1 ? 3 4 ? 5 4 ? 7 4 ? 9 4 ? 11 4 ? 13 4 ! 4003 2
result:
ok correct! (9 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
78 8 951 614 927 614 957 614 957 604 937 614 942 619 951 610 927 604 10 1 10 1 10 1 15 1 25 4 10 1 7 562 260 602 250 582 255 587 260 602 260 562 250 577 260 10 1 10 1 10 1 5 1 10 1 3 454 98 494 68 455 68 117 4 3 526 589 566 559 527 559 117 4 3 854 496 854 466 894 466 30 1 3 797 264 827 254 857 264 1...
output:
? 927 1 ? 957 1 ? 937 1 ? 942 1 ? 3803 4 ? 3805 4 ! 317 1 ? 562 1 ? 602 1 ? 577 1 ? 582 1 ? 587 1 ! 375 1 ? 455 1 ! 585 1 ? 527 1 ! 585 1 ? 854 1 ! 600 1 ? 827 1 ! 300 1 ? 719 1 ! 600 1 ? 162 1 ! 400 1 ? 742 1 ? 792 1 ? 2987 4 ? 2989 4 ? 3007 4 ? 3009 4 ! 275 1 ? 932 1 ? 987 1 ? 3747 4 ? 3749 4 ? 37...
result:
ok correct! (78 test cases)
Test #4:
score: 0
Accepted
time: 6ms
memory: 3796kb
input:
34 24 123 815 168 800 133 795 27 827 153 805 28 830 178 780 138 810 78 830 192 772 148 790 88 810 43 825 183 795 103 805 163 785 118 800 93 825 63 835 73 815 58 820 198 790 48 840 108 820 10 3 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 95 6 15 2 15 1 24...
output:
? 28 1 ? 43 1 ? 48 1 ? 58 1 ? 63 1 ? 73 1 ? 78 1 ? 88 1 ? 93 1 ? 103 1 ? 108 1 ? 118 1 ? 123 1 ? 133 1 ? 138 1 ? 148 1 ? 153 1 ? 163 1 ? 168 1 ? 178 1 ? 183 1 ? 192 1 ! 1925 1 ? 54 1 ? 69 1 ? 74 1 ? 84 1 ? 89 1 ? 99 1 ? 104 1 ? 114 1 ? 119 1 ? 129 1 ? 134 1 ? 144 1 ? 149 1 ? 159 1 ? 164 1 ? 174 1 ? ...
result:
ok correct! (34 test cases)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
47 50 227 745 183 763 230 745 208 936 223 745 220 936 232 937 183 759 183 751 226 745 207 762 207 754 207 748 224 745 207 756 207 764 207 758 230 936 232 745 231 936 222 745 221 745 228 745 183 755 224 936 208 747 183 767 183 757 207 750 231 745 183 761 225 936 183 765 229 745 227 936 183 749 207 76...
output:
? 183 1 ? 232 1 ? 827 4 ? 829 4 ? 831 4 ? 833 4 ? 220 1 ? 883 4 ? 885 4 ? 887 4 ? 889 4 ? 891 4 ? 893 4 ? 895 4 ? 897 4 ? 899 4 ? 901 4 ? 903 4 ? 905 4 ? 907 4 ? 909 4 ? 911 4 ? 913 4 ? 915 4 ? 917 4 ? 919 4 ? 921 4 ? 923 4 ? 925 4 ! 1600 1 ? 499 1 ? 1199 4 ? 1201 4 ? 1203 4 ? 1205 4 ? 1207 4 ? 1209...
result:
ok correct! (47 test cases)
Test #6:
score: 0
Accepted
time: 3ms
memory: 3816kb
input:
6 200 359 161 391 193 374 252 387 189 378 252 362 165 395 197 446 252 358 161 377 252 384 252 382 252 352 155 397 199 444 247 412 252 395 252 401 252 391 252 419 252 421 252 401 203 431 233 444 252 434 237 385 252 450 252 421 223 367 252 428 252 379 252 419 221 402 252 430 252 387 252 353 252 396 19...
output:
? 350 1 ? 450 1 ? 1407 4 ? 1409 4 ? 1411 4 ? 1413 4 ? 1415 4 ? 1417 4 ? 1419 4 ? 1421 4 ? 1423 4 ? 1425 4 ? 1427 4 ? 1429 4 ? 1431 4 ? 1433 4 ? 1435 4 ? 1437 4 ? 1439 4 ? 1441 4 ? 1443 4 ? 1445 4 ? 1447 4 ? 1449 4 ? 1451 4 ? 1453 4 ? 1455 4 ? 1457 4 ? 1459 4 ? 1461 4 ? 1463 4 ? 1465 4 ? 1467 4 ? 146...
result:
ok correct! (6 test cases)
Test #7:
score: 0
Accepted
time: 2ms
memory: 3948kb
input:
30 57 482 166 584 167 538 167 506 167 618 166 526 168 563 166 629 168 547 168 475 167 583 167 582 167 546 168 471 167 628 168 593 166 634 167 521 166 557 167 539 167 476 167 470 168 505 167 580 168 465 166 514 167 653 167 617 167 570 167 562 166 619 166 472 167 660 166 520 166 491 167 558 167 635 16...
output:
? 465 1 ? 664 1 ? 1875 4 ? 1877 4 ? 1879 4 ? 1881 4 ? 471 1 ? 472 1 ? 475 1 ? 476 1 ? 482 1 ? 483 1 ? 490 1 ? 491 1 ? 505 1 ? 506 1 ? 514 1 ? 515 1 ? 520 1 ? 521 1 ? 526 1 ? 527 1 ? 538 1 ? 539 1 ? 546 1 ? 547 1 ? 557 1 ? 558 1 ? 562 1 ? 563 1 ? 570 1 ? 571 1 ? 579 1 ? 580 1 ? 582 1 ? 583 1 ? 584 1 ...
result:
ok correct! (30 test cases)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
12 20 69 340 411 520 513 767 826 881 199 805 622 48 945 965 677 968 388 519 825 72 122 508 448 348 982 932 838 965 448 182 716 450 8 857 346 351 792 433 224 449 117548 223 47161313 84517 7549481525 24425413 73924992225 225575873 42227227870624 157226383481 1076496201908 3834789841 6882360591313 2278...
output:
? 69 1 ? 122 1 ? 199 1 ? 224 1 ? 346 1 ? 388 1 ? 411 1 ? 1791 4 ? 1793 4 ? 513 1 ? 622 1 ? 677 1 ? 716 1 ? 792 1 ? 825 1 ? 826 1 ? 838 1 ? 945 1 ! 566163 2 ? 100 1 ? 119 1 ? 123 1 ? 141 1 ? 152 1 ? 160 1 ? 178 1 ? 180 1 ? 183 1 ? 184 1 ? 186 1 ? 204 1 ? 213 1 ? 221 1 ? 242 1 ? 274 1 ? 279 1 ? 280 1 ...
result:
ok correct! (12 test cases)
Test #9:
score: 0
Accepted
time: 3ms
memory: 3976kb
input:
47 100 336 60 627 234 594 968 147 351 511 151 134 433 343 690 97 981 734 678 968 833 962 4 34 977 889 172 227 46 138 713 578 695 193 895 835 513 562 707 504 571 490 366 108 605 440 145 141 743 155 214 143 633 839 995 493 751 480 254 317 587 491 988 537 549 915 465 403 233 343 112 12 236 965 847 710 ...
output:
? 7 1 ? 12 1 ? 33 1 ? 135 4 ? 137 4 ? 38 1 ? 43 1 ? 97 1 ? 104 1 ? 108 1 ? 132 1 ? 134 1 ? 138 1 ? 563 4 ? 565 4 ? 143 1 ? 147 1 ? 155 1 ? 193 1 ? 227 1 ? 235 1 ? 252 1 ? 253 1 ? 268 1 ? 291 1 ? 295 1 ? 315 1 ? 317 1 ? 332 1 ? 336 1 ? 1371 4 ? 1373 4 ? 352 1 ? 355 1 ? 360 1 ? 398 1 ? 403 1 ? 405 1 ?...
result:
ok correct! (47 test cases)
Test #10:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
5 183 529 552 529 553 526 556 534 552 536 555 528 547 526 553 540 545 535 552 534 555 530 552 535 550 537 550 526 550 534 547 535 556 526 551 530 549 530 551 525 560 525 558 528 551 535 558 537 547 538 560 531 553 533 547 526 558 530 546 531 558 535 554 527 560 534 549 532 557 534 553 540 557 527 54...
output:
? 524 1 ? 540 1 ? 2099 4 ? 2101 4 ? 2103 4 ? 2105 4 ? 2107 4 ? 2109 4 ? 2111 4 ? 2113 4 ? 2115 4 ? 2117 4 ? 2119 4 ? 2121 4 ? 2123 4 ? 2125 4 ? 2127 4 ? 2129 4 ? 2131 4 ? 2133 4 ? 2135 4 ? 2137 4 ? 2139 4 ? 2141 4 ? 2143 4 ? 2145 4 ? 2147 4 ? 2149 4 ? 2151 4 ? 2153 4 ? 2155 4 ? 2157 4 ! 287 2 ? 101 ...
result:
ok correct! (5 test cases)
Test #11:
score: 0
Accepted
time: 2ms
memory: 3940kb
input:
5 195 548 38 540 29 547 28 544 29 542 33 549 37 541 26 546 33 543 38 545 33 545 26 546 24 539 35 542 26 545 35 536 28 541 28 538 33 539 31 540 24 540 25 538 32 535 36 544 34 542 38 542 28 547 32 539 25 550 25 536 30 545 30 543 23 537 34 534 36 541 29 540 37 544 26 535 29 548 36 539 27 546 32 549 29 ...
output:
? 534 1 ? 550 1 ? 2139 4 ? 2141 4 ? 2143 4 ? 2145 4 ? 2147 4 ? 2149 4 ? 2151 4 ? 2153 4 ? 2155 4 ? 2157 4 ? 2159 4 ? 2161 4 ? 2163 4 ? 2165 4 ? 2167 4 ? 2169 4 ? 2171 4 ? 2173 4 ? 2175 4 ? 2177 4 ? 2179 4 ? 2181 4 ? 2183 4 ? 2185 4 ? 2187 4 ? 2189 4 ? 2191 4 ? 2193 4 ? 2195 4 ? 2197 4 ! 287 2 ? 962 ...
result:
ok correct! (5 test cases)
Test #12:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
6 191 562 409 558 414 549 405 549 414 550 403 562 398 553 412 554 410 563 410 548 401 548 413 548 412 552 407 554 408 556 410 552 403 552 412 549 411 563 414 558 404 559 402 550 411 560 403 556 408 562 404 548 414 562 412 559 403 551 400 562 399 547 407 560 406 548 410 562 402 553 414 558 408 553 40...
output:
? 547 1 ? 563 1 ? 2191 4 ? 2193 4 ? 2195 4 ? 2197 4 ? 2199 4 ? 2201 4 ? 2203 4 ? 2205 4 ? 2207 4 ? 2209 4 ? 2211 4 ? 2213 4 ? 2215 4 ? 2217 4 ? 2219 4 ? 2221 4 ? 2223 4 ? 2225 4 ? 2227 4 ? 2229 4 ? 2231 4 ? 2233 4 ? 2235 4 ? 2237 4 ? 2239 4 ? 2241 4 ? 2243 4 ? 2245 4 ? 2247 4 ? 2249 4 ! 287 2 ? 973 ...
result:
ok correct! (6 test cases)
Test #13:
score: 0
Accepted
time: 3ms
memory: 3904kb
input:
100 4 432 383 378 564 879 428 360 237 55425 173 20674 173 9 403 900 991 82 251 377 546 339 621 826 476 904 167 637 184 206 569 464 127483 2814 5064736823 19572978 1686763227553 5774028510 48297246268163 95848873266 57736816891 86762722 82744792 117015 554528 807 7 750 849 303 479 508 268 604 865 208...
output:
? 378 1 ? 432 1 ! 41469 1 ? 184 1 ? 251 1 ? 403 1 ? 476 1 ? 546 1 ? 569 1 ? 621 1 ! 301579 1 ? 303 1 ? 508 1 ? 604 1 ? 750 1 ? 791 1 ! 324517 1 ? 228 1 ? 322 1 ! 30319 1 ? 90 1 ? 146 1 ? 179 1 ? 182 1 ? 296 1 ? 314 1 ? 318 1 ? 326 1 ? 412 1 ? 445 1 ? 446 1 ? 451 1 ? 469 1 ? 500 1 ? 546 1 ? 623 1 ? 6...
result:
ok correct! (100 test cases)
Test #14:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
10 9 243 378 841 782 148 442 136 745 35 882 560 780 385 85 443 884 953 473 28049 204 89873 204 25756 51 81469 102 19903 35 14729 199 87053 393 17 556 767 642 508 179 298 744 572 69 787 592 841 213 929 11 152 949 762 520 41 523 827 371 990 757 661 981 146 419 519 350 27 957 818 340721 4746 3276445 40...
output:
? 136 1 ? 148 1 ? 243 1 ? 385 1 ? 443 1 ? 560 1 ? 841 1 ! 558135 2 ? 69 1 ? 179 1 ? 213 1 ? 350 1 ? 371 1 ? 419 1 ? 520 1 ? 523 1 ? 556 1 ? 592 1 ? 642 1 ? 744 1 ? 757 1 ? 949 1 ? 957 1 ! 504173 1 ? 1 1 ? 6 1 ? 11 1 ? 22 1 ? 35 1 ? 41 1 ? 56 1 ? 72 1 ? 81 1 ? 92 1 ? 96 1 ? 101 1 ? 113 1 ? 114 1 ? 13...
result:
ok correct! (10 test cases)
Test #15:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
1 999 418 860 741 570 398 686 307 967 125 323 595 219 949 428 230 577 401 658 192 266 63 130 526 928 958 736 574 300 248 530 360 734 982 201 542 337 110 305 344 477 855 188 331 887 1000 410 267 449 231 634 726 482 661 708 625 719 345 3 976 556 974 446 989 64 688 137 677 862 563 762 412 960 434 947 3...
output:
? 0 1 ? 1 1 ? 2 1 ? 11 4 ? 13 4 ? 5 1 ? 6 1 ? 31 4 ? 33 4 ? 35 4 ? 37 4 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 16 1 ? 18 1 ? 19 1 ? 87 4 ? 89 4 ? 24 1 ? 25 1 ? 26 1 ? 28 1 ? 115 4 ? 117 4 ? 123 4 ? 125 4 ? 143 4 ? 145 4 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 187 4 ? 189 4 ? 191 4 ? 193 4 ? 49 1 ?...
result:
ok correct! (1 test case)
Test #16:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
100 8 965 686 363 95 657 171 462 37 13 372 46 611 839 946 375 291 92791 350 515383 793 363975 793 45734 61 42585 61 10355 22 7 384 464 164 845 825 46 292 87 14 238 329 616 458 275 95698 139 95758 165 6914 13 4993 13 2610 13 8 334 854 907 218 140 497 950 599 247 987 849 255 492 689 53 952 119329 281 ...
output:
? 46 1 ? 363 1 ? 375 1 ? 462 1 ? 657 1 ? 839 1 ! 485819 1 ? 164 1 ? 292 1 ? 329 1 ? 384 1 ? 458 1 ! 474169 2 ? 140 1 ? 247 1 ? 334 1 ? 492 1 ? 849 1 ? 907 1 ! 364259 1 ? 44 1 ? 92 1 ? 99 1 ? 102 1 ? 219 1 ? 277 1 ? 434 1 ? 447 1 ? 631 1 ? 730 1 ? 741 1 ? 800 1 ? 803 1 ? 855 1 ! 672417 2 ? 252 1 ? 30...
result:
ok correct! (100 test cases)
Test #17:
score: 0
Accepted
time: 3ms
memory: 3960kb
input:
10 127 381 549 297 504 961 486 673 617 737 870 639 562 438 661 210 337 884 488 670 963 887 728 271 264 992 860 260 650 187 121 685 794 448 797 572 932 352 480 927 172 880 121 470 933 485 258 273 288 698 340 539 671 149 299 829 56 371 971 576 105 862 199 926 209 585 837 378 125 492 202 359 453 274 57...
output:
? 28 1 ? 41 1 ? 42 1 ? 54 1 ? 60 1 ? 67 1 ? 85 1 ? 91 1 ? 94 1 ? 95 1 ? 133 1 ? 138 1 ? 147 1 ? 149 1 ? 152 1 ? 160 1 ? 170 1 ? 185 1 ? 187 1 ? 210 1 ? 213 1 ? 222 1 ? 244 1 ? 247 1 ? 260 1 ? 268 1 ? 271 1 ? 273 1 ? 274 1 ? 275 1 ? 284 1 ? 297 1 ? 313 1 ? 325 1 ? 333 1 ? 334 1 ? 341 1 ? 344 1 ? 352 ...
result:
ok correct! (10 test cases)
Test #18:
score: 0
Accepted
time: 8ms
memory: 3944kb
input:
1 997 31 967 561 563 77 899 278 232 905 414 944 891 688 470 35 589 72 942 912 459 797 102 496 946 508 427 925 744 217 287 86 2 702 732 965 675 901 433 59 200 732 623 139 180 671 907 195 275 2 631 632 574 318 798 293 785 987 60 638 532 627 641 762 432 792 837 452 842 205 700 50 874 92 920 45 76 701 8...
output:
? 1 1 ? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 44 1 ?...
result:
ok correct! (1 test case)
Test #19:
score: 0
Accepted
time: 6ms
memory: 3936kb
input:
100 22 440 908 780 215 694 883 610 182 854 925 209 611 697 442 555 903 411 296 641 308 957 488 655 836 474 34 736 125 2 734 740 68 204 1000 536 750 584 558 96 296 518 344 761 693 469436 5037 86355113 277035 107224476167 332586540 876958338859 1648151076 505945614769 921273210 9254733032 17060615 508...
output:
? 96 1 ? 204 1 ? 209 1 ? 411 1 ? 440 1 ? 474 1 ? 518 1 ? 536 1 ? 555 1 ? 584 1 ? 610 1 ? 641 1 ? 655 1 ? 694 1 ? 697 1 ? 736 1 ? 740 1 ? 761 1 ? 780 1 ? 854 1 ! 845077 2 ? 283 1 ? 534 1 ? 603 1 ? 727 1 ! 136715 1 ? 75 1 ? 96 1 ? 146 1 ? 206 1 ? 224 1 ? 250 1 ? 284 1 ? 332 1 ? 410 1 ? 454 1 ? 676 1 ?...
result:
ok correct! (100 test cases)
Test #20:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
10 215 866 948 174 934 755 317 949 514 727 601 975 939 354 571 564 669 827 916 716 597 924 608 878 628 78 982 402 504 516 660 465 345 357 556 741 143 967 133 414 82 297 81 785 123 48 119 338 647 95 452 958 680 441 817 270 30 587 615 137 446 836 389 358 173 495 398 94 140 922 411 533 933 444 470 352 ...
output:
? 7 1 ? 14 1 ? 25 1 ? 36 1 ? 39 1 ? 43 1 ? 48 1 ? 49 1 ? 57 1 ? 69 1 ? 75 1 ? 78 1 ? 80 1 ? 85 1 ? 91 1 ? 92 1 ? 93 1 ? 94 1 ? 95 1 ? 102 1 ? 105 1 ? 111 1 ? 113 1 ? 114 1 ? 115 1 ? 117 1 ? 122 1 ? 123 1 ? 133 1 ? 134 1 ? 137 1 ? 140 1 ? 148 1 ? 151 1 ? 165 1 ? 167 1 ? 173 1 ? 174 1 ? 187 1 ? 190 1 ...
result:
ok correct! (10 test cases)
Test #21:
score: 0
Accepted
time: 2ms
memory: 3948kb
input:
1 1000 903 972 368 25 864 957 138 863 388 590 405 404 399 134 629 850 884 984 423 555 213 440 749 211 706 435 140 139 506 853 180 993 280 110 365 362 406 645 490 961 238 159 232 914 267 94 830 951 622 933 631 436 771 112 825 149 38 82 572 322 411 147 329 161 511 500 748 217 906 209 800 887 990 938 2...
output:
? 1 1 ? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 44 1 ?...
result:
ok correct! (1 test case)
Test #22:
score: 0
Accepted
time: 7ms
memory: 3972kb
input:
100 9 387 4 620 974 157 175 47 935 157 893 978 751 978 543 387 610 620 842 208 1 157601 220 82556 115 69704 115 333881609 550812 417151019 550812 176374043 282104 38 678 102 793 490 747 91 930 210 409 297 585 383 922 937 573 945 770 164 963 160 741 69 63 8 678 201 656 412 51 3 585 10 300 313 619 305...
output:
? 978 1 ? 627 4 ? 629 4 ? 1547 4 ? 1549 4 ? 2479 4 ? 2481 4 ! 999589 2 ? 992 1 ? 251 4 ? 253 4 ? 1199 4 ? 1201 4 ? 1635 4 ? 1637 4 ? 1791 4 ? 1793 4 ? 2291 4 ? 2293 4 ? 2339 4 ? 2341 4 ? 619 1 ? 2531 4 ? 2533 4 ? 656 1 ? 2711 4 ? 2713 4 ? 2963 4 ? 2965 4 ? 2987 4 ? 2989 4 ? 3079 4 ? 3081 4 ? 793 1 ?...
result:
ok correct! (100 test cases)
Test #23:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
10 265 711 246 635 106 363 296 298 516 148 548 20 264 717 993 976 382 212 151 338 427 107 918 15 648 573 138 733 967 828 489 444 793 758 988 740 898 227 906 592 734 625 702 728 912 824 323 821 483 403 571 188 872 817 384 637 685 76 375 500 685 725 299 960 630 805 902 450 638 289 548 510 181 788 975 ...
output:
? 5 1 ? 990 1 ? 59 4 ? 61 4 ? 79 4 ? 81 4 ? 131 4 ? 133 4 ? 179 4 ? 181 4 ? 183 4 ? 185 4 ? 259 4 ? 261 4 ? 287 4 ? 289 4 ? 303 4 ? 305 4 ? 343 4 ? 345 4 ? 407 4 ? 409 4 ? 427 4 ? 429 4 ? 479 4 ? 481 4 ? 495 4 ? 497 4 ? 515 4 ? 517 4 ? 591 4 ? 593 4 ? 651 4 ? 653 4 ? 663 4 ? 665 4 ? 715 4 ? 717 4 ? ...
result:
ok correct! (10 test cases)
Test #24:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 1000 223 436 120 685 243 500 776 484 710 948 428 611 155 840 733 209 193 469 730 884 889 899 271 55 5 495 435 573 757 224 477 493 240 827 515 664 764 929 495 443 397 912 685 352 236 819 691 276 538 348 101 934 592 69 741 90 720 693 85 849 130 885 271 752 531 849 247 41 513 181 298 458 189 475 712 ...
output:
? 2 1 ? 999 1 ? 19 4 ? 21 4 ? 27 4 ? 29 4 ? 35 4 ? 37 4 ? 43 4 ? 45 4 ? 47 4 ? 49 4 ? 51 4 ? 53 4 ? 83 4 ? 85 4 ? 107 4 ? 109 4 ? 115 4 ? 117 4 ? 135 4 ? 137 4 ? 159 4 ? 161 4 ? 219 4 ? 221 4 ? 223 4 ? 225 4 ? 231 4 ? 233 4 ? 259 4 ? 261 4 ? 275 4 ? 277 4 ? 283 4 ? 285 4 ? 295 4 ? 297 4 ? 303 4 ? 30...
result:
ok correct! (1 test case)
Test #25:
score: 0
Accepted
time: 4ms
memory: 3732kb
input:
100 4 1 1000 0 0 517 791 377 129 376871 377 92713 129 9 168 332 1 0 262 723 263 932 291 27 258 311 71 543 0 1000 70 339 262932 263 74399631 76270 82331595 106778 9302862573 14567570 7300316613 14567570 40056563 86790 1165514 4785 7 494 277 1 1000 0 0 696 595 277 739 435 88 54 196 434912 435 12525677...
output:
? 1 1 ? 377 1 ! 747723 2 ? 1 1 ? 70 1 ? 71 1 ? 168 1 ? 258 1 ? 262 1 ? 263 1 ! 389725 2 ? 1 1 ? 54 1 ? 277 1 ? 435 1 ? 494 1 ! 362785 1 ? 985 1 ? 999 1 ! 116785 1 ? 117 1 ? 151 1 ? 264 1 ? 284 1 ? 292 1 ? 353 1 ? 464 1 ? 482 1 ? 491 1 ? 497 1 ? 610 1 ? 638 1 ? 665 1 ? 781 1 ? 857 1 ? 897 1 ? 999 1 !...
result:
ok correct! (100 test cases)
Test #26:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
10 9 496 52 825 592 0 0 1 1000 853 985 7 125 526 89 736 767 943 521 123987 124 8796609 8804 446131323 638716 2385697 3692 2044027 3692 1441987 8307 70740 767 17 407 499 296 912 463 41 575 862 293 242 219 602 717 283 29 11 371 775 999 1000 875 460 440 332 247 733 130 817 667 304 1000 0 56 683 457704 ...
output:
? 1 1 ? 7 1 ? 496 1 ? 526 1 ? 736 1 ? 825 1 ? 853 1 ! 1215909 2 ? 56 1 ? 130 1 ? 219 1 ? 247 1 ? 293 1 ? 296 1 ? 371 1 ? 407 1 ? 440 1 ? 463 1 ? 575 1 ? 667 1 ? 717 1 ? 875 1 ? 999 1 ! 1163041 2 ? 1 1 ? 3 1 ? 12 1 ? 14 1 ? 17 1 ? 31 1 ? 36 1 ? 37 1 ? 50 1 ? 51 1 ? 53 1 ? 56 1 ? 239 4 ? 241 4 ? 61 1 ...
result:
ok correct! (10 test cases)
Test #27:
score: 0
Accepted
time: 3ms
memory: 3852kb
input:
1 1000 665 114 208 428 52 111 52 950 170 733 664 624 466 464 727 67 144 115 435 721 594 778 227 293 965 378 796 636 454 64 999 1000 594 494 920 647 486 735 862 14 900 530 675 978 595 493 738 63 97 44 566 458 173 250 832 229 712 694 487 446 697 463 908 497 756 590 306 292 537 200 926 106 361 118 83 6...
output:
? 8 1 ? 35 4 ? 37 4 ? 39 4 ? 41 4 ? 43 4 ? 45 4 ? 47 4 ? 49 4 ? 13 1 ? 14 1 ? 63 4 ? 65 4 ? 18 1 ? 75 4 ? 77 4 ? 79 4 ? 81 4 ? 23 1 ? 25 1 ? 103 4 ? 105 4 ? 27 1 ? 29 1 ? 119 4 ? 121 4 ? 32 1 ? 135 4 ? 137 4 ? 36 1 ? 147 4 ? 149 4 ? 151 4 ? 153 4 ? 40 1 ? 41 1 ? 167 4 ? 169 4 ? 175 4 ? 177 4 ? 179 4...
result:
ok correct! (1 test case)
Test #28:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
100 8 954 724 987 177 348 574 637 423 538 43 343 0 161 1000 625 271 57136 61 2221541 2379 1209840657 1780529 5781057558027 10392947773 2500358554723 6509078017 1496781 81269 7 148 0 855 342 748 661 234 593 563 403 960 206 175 1000 403219 406 36573660 38773 8602326801 19929322 12574573 59276 9433 58 ...
output:
? 343 1 ? 348 1 ? 538 1 ? 625 1 ? 637 1 ? 954 1 ! 366680 1 ? 175 1 ? 234 1 ? 563 1 ? 748 1 ? 855 1 ! 769689 2 ? 267 1 ? 373 1 ? 430 1 ? 464 1 ? 571 1 ? 642 1 ! 622561 2 ? 298 1 ? 370 1 ? 528 1 ? 534 1 ? 544 1 ? 633 1 ? 668 1 ? 712 1 ? 732 1 ? 741 1 ? 811 1 ? 849 1 ? 884 1 ? 897 1 ! 921351 2 ? 84 1 ?...
result:
ok correct! (100 test cases)
Test #29:
score: 0
Accepted
time: 4ms
memory: 3764kb
input:
10 127 350 974 270 995 385 592 421 275 740 716 312 286 940 953 208 113 641 631 92 795 562 757 317 188 327 777 629 930 386 161 972 703 248 951 515 856 648 983 71 551 64 516 687 859 830 394 513 166 201 337 986 269 959 58 253 522 958 879 116 442 175 494 135 556 667 837 233 409 507 385 637 235 240 940 1...
output:
? 33 1 ? 39 1 ? 64 1 ? 68 1 ? 71 1 ? 73 1 ? 74 1 ? 88 1 ? 92 1 ? 98 1 ? 104 1 ? 105 1 ? 113 1 ? 116 1 ? 120 1 ? 135 1 ? 138 1 ? 162 1 ? 171 1 ? 175 1 ? 177 1 ? 179 1 ? 188 1 ? 190 1 ? 198 1 ? 201 1 ? 203 1 ? 208 1 ? 229 1 ? 233 1 ? 235 1 ? 240 1 ? 245 1 ? 247 1 ? 248 1 ? 253 1 ? 256 1 ? 263 1 ? 268 ...
result:
ok correct! (10 test cases)
Test #30:
score: 0
Accepted
time: 7ms
memory: 3896kb
input:
1 1000 794 107 148 421 837 104 270 943 620 726 82 617 982 457 309 60 939 108 599 714 961 771 586 286 506 371 154 629 986 57 684 993 411 487 239 640 740 728 174 7 857 523 482 971 824 486 296 56 806 37 543 451 631 243 770 222 383 687 825 439 11 456 766 490 517 583 963 285 790 193 767 99 862 111 998 10...
output:
? 1 1 ? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 44 1 ?...
result:
ok correct! (1 test case)
Test #31:
score: 0
Accepted
time: 7ms
memory: 3836kb
input:
100 22 780 465 411 857 2 577 854 0 736 785 518 216 641 888 209 532 655 84 780 1000 204 856 697 202 584 2 694 884 440 382 555 863 740 517 761 111 610 28 96 100 536 30 474 926 397338 8441 332712739182 3137815135 12364112649397 112961344860 4046367253037 19318027092 1010316051029 4492564440 32061030402...
output:
? 96 1 ? 204 1 ? 209 1 ? 411 1 ? 440 1 ? 474 1 ? 518 1 ? 536 1 ? 555 1 ? 584 1 ? 610 1 ? 641 1 ? 655 1 ? 694 1 ? 697 1 ? 736 1 ? 740 1 ? 761 1 ? 3119 4 ? 3121 4 ! 605895 2 ? 1707 4 ? 1709 4 ? 697 1 ? 744 1 ! 310828 1 ? 34 1 ? 52 1 ? 66 1 ? 160 1 ? 211 1 ? 1103 4 ? 1105 4 ? 340 1 ? 536 1 ? 543 1 ? 56...
result:
ok correct! (100 test cases)
Test #32:
score: 0
Accepted
time: 6ms
memory: 4020kb
input:
10 215 688 594 420 534 474 751 376 873 338 798 866 633 590 926 620 389 505 589 134 797 122 833 490 825 968 545 735 948 284 386 165 83 805 933 682 992 48 909 117 136 495 156 686 982 57 249 43 383 876 270 666 859 859 442 133 151 137 672 817 223 609 812 884 135 36 997 941 244 820 874 936 551 878 943 94...
output:
? 7 1 ? 14 1 ? 25 1 ? 36 1 ? 39 1 ? 43 1 ? 48 1 ? 49 1 ? 57 1 ? 69 1 ? 75 1 ? 78 1 ? 80 1 ? 85 1 ? 91 1 ? 92 1 ? 93 1 ? 94 1 ? 95 1 ? 102 1 ? 105 1 ? 111 1 ? 113 1 ? 114 1 ? 115 1 ? 117 1 ? 122 1 ? 123 1 ? 133 1 ? 134 1 ? 137 1 ? 140 1 ? 148 1 ? 151 1 ? 165 1 ? 167 1 ? 173 1 ? 174 1 ? 187 1 ? 190 1 ...
result:
ok correct! (10 test cases)
Test #33:
score: 0
Accepted
time: 4ms
memory: 3892kb
input:
1 1000 549 618 788 304 884 621 824 784 2 1000 597 108 247 268 799 665 715 617 723 11 185 955 509 439 418 354 411 96 68 668 806 733 660 238 623 85 475 998 118 718 620 202 760 756 412 239 573 669 595 688 761 274 677 482 610 503 76 38 903 286 895 269 589 235 995 142 245 440 808 532 927 626 626 614 724 ...
output:
? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 44 1 ? 45 1 ...
result:
ok correct! (1 test case)
Test #34:
score: 0
Accepted
time: 6ms
memory: 3896kb
input:
1 999 474 949 631 264 972 946 392 785 284 569 729 460 649 300 451 903 974 950 278 557 806 614 64 129 606 214 735 472 949 900 417 835 664 330 241 483 285 571 924 850 682 366 406 813 164 329 449 899 939 880 646 294 542 86 32 65 764 530 640 282 149 299 166 333 712 426 563 128 517 36 470 941 476 953 920...
output:
? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 44 1 ? 45 1 ...
result:
ok correct! (1 test case)
Test #35:
score: 0
Accepted
time: 2ms
memory: 3880kb
input:
1 999 169 662 326 348 667 665 87 826 978 43 424 152 344 312 146 708 669 661 972 55 501 997 758 483 301 398 430 140 644 711 112 776 359 282 935 129 979 41 619 761 377 246 101 798 858 283 144 712 634 731 341 318 237 526 726 547 459 82 335 330 843 313 860 279 407 186 258 484 212 576 165 670 171 658 615...
output:
? 0 1 ? 1 1 ? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? ...
result:
ok correct! (1 test case)
Test #36:
score: 0
Accepted
time: 8ms
memory: 3948kb
input:
1 999 179 641 22 955 818 638 261 477 369 261 575 152 4 991 202 595 820 642 375 249 652 306 909 820 47 905 581 164 795 592 236 527 510 22 412 175 368 263 770 542 528 58 247 505 489 21 204 591 785 572 7 985 111 777 877 756 610 222 13 973 994 990 487 25 558 118 90 819 136 727 183 633 177 645 766 534 54...
output:
? 1 1 ? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? 44 1 ?...
result:
ok correct! (1 test case)
Test #37:
score: 0
Accepted
time: 8ms
memory: 3952kb
input:
1 999 806 613 649 299 192 616 888 777 996 993 551 103 631 263 829 659 194 612 497 6 26 948 283 434 674 349 545 91 169 662 863 727 616 233 460 80 995 991 144 712 598 197 874 749 383 234 831 663 159 682 634 269 738 477 251 498 516 33 640 281 368 264 385 230 568 137 717 435 763 527 810 621 804 609 140 ...
output:
? 0 1 ? 1 1 ? 2 1 ? 3 1 ? 4 1 ? 5 1 ? 6 1 ? 7 1 ? 8 1 ? 9 1 ? 10 1 ? 11 1 ? 12 1 ? 13 1 ? 14 1 ? 15 1 ? 16 1 ? 17 1 ? 18 1 ? 19 1 ? 20 1 ? 21 1 ? 22 1 ? 23 1 ? 24 1 ? 25 1 ? 26 1 ? 27 1 ? 28 1 ? 29 1 ? 30 1 ? 31 1 ? 32 1 ? 33 1 ? 34 1 ? 35 1 ? 36 1 ? 37 1 ? 38 1 ? 39 1 ? 40 1 ? 41 1 ? 42 1 ? 43 1 ? ...
result:
ok correct! (1 test case)
Extra Test:
score: 0
Extra Test Passed