QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#63524 | #2727. Gradient Descent | Baltinic | 25 ✓ | 8ms | 3328kb | C++14 | 1.1kb | 2022-11-22 15:01:45 | 2022-11-22 15:01:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 150 + 10;
int n, m, k;
ll ask(int x, int y) {
cout << "? " << x << " " << y << endl;
ll score = 0;
// for(int i = 1; i <= k; i++) score += abs(::x[i] - x) + abs(::y[i] - y);
cin >> score;
return score;
}
int main() {
cin >> n >> m >> k;
// for(int i = 1; i <= k; i++) cin >> x[i] >> y[i];
int u = 1, d = n - 1, l = 1, r = m - 1, x = n, y = m;
while (u <= d || l <= r) {
int m1 = (u + d) / 2, m2 = (l + r) / 2;
if (u > d)
m1 = 1;
if (l > r)
m2 = 1;
ll v1 = ask(m1, m2);
if (u <= d) {
ll v2 = ask(m1 + 1, m2);
if (v1 <= v2)
x = m1, d = m1 - 1;
else
u = m1 + 1;
}
if (l <= r) {
ll v3 = ask(m1, m2 + 1);
if (v1 <= v3)
y = m2, r = m2 - 1;
else
l = m2 + 1;
}
}
ll ans = ask(x, y);
cout << "! " << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 3ms
memory: 3252kb
input:
1 90 90 2900 2800 700 600 400 500 200 100 100 200 100 0 0 100 0
output:
? 1 45 ? 1 46 ? 1 67 ? 1 68 ? 1 78 ? 1 79 ? 1 72 ? 1 73 ? 1 75 ? 1 76 ? 1 73 ? 1 74 ? 1 74 ? 1 75 ? 1 74 ! 0
result:
ok Solution answered 0 ans asked 15 questions
Test #2:
score: 0
Accepted
time: 2ms
memory: 3324kb
input:
1 90 90 2242 2233 2470 2507 2235 2244 2219 2218 2220 2225 2218 2219 2218
output:
? 1 45 ? 1 46 ? 1 67 ? 1 68 ? 1 56 ? 1 57 ? 1 50 ? 1 51 ? 1 53 ? 1 54 ? 1 51 ? 1 52 ? 1 51 ! 2218
result:
ok Solution answered 2218 ans asked 13 questions
Test #3:
score: 0
Accepted
time: 0ms
memory: 3308kb
input:
1 90 90 2312 2292 2428 2470 2206 2206 2238 2226 2214 2210 2210 2208 2208 2206 2206
output:
? 1 45 ? 1 46 ? 1 67 ? 1 68 ? 1 56 ? 1 57 ? 1 50 ? 1 51 ? 1 53 ? 1 54 ? 1 54 ? 1 55 ? 1 55 ? 1 56 ? 1 56 ! 2206
result:
ok Solution answered 2206 ans asked 15 questions
Test #4:
score: 0
Accepted
time: 3ms
memory: 3224kb
input:
1 60 90 1368 1363 1675 1730 1401 1424 1357 1360 1363 1358 1358 1357 1357
output:
? 1 30 ? 1 31 ? 1 45 ? 1 46 ? 1 37 ? 1 38 ? 1 33 ? 1 34 ? 1 31 ? 1 32 ? 1 32 ? 1 33 ? 1 33 ! 1357
result:
ok Solution answered 1357 ans asked 13 questions
Test #5:
score: 0
Accepted
time: 4ms
memory: 3268kb
input:
1 60 90 1410 1410 1920 1864 1586 1546 1456 1432 1418 1414 1414 1410 1410
output:
? 1 30 ? 1 31 ? 1 15 ? 1 16 ? 1 22 ? 1 23 ? 1 26 ? 1 27 ? 1 28 ? 1 29 ? 1 29 ? 1 30 ? 1 30 ! 1410
result:
ok Solution answered 1410 ans asked 13 questions
Subtask #2:
score: 5
Accepted
Test #6:
score: 5
Accepted
time: 6ms
memory: 3224kb
input:
1 10000000 90 315667100 315667000 65667100 65667000 59332900 59333000 3167100 3167000 28082900 28083000 12457900 12458000 4645400 4645500 739100 739200 1214000 1213900 237500 237400 250800 250900 6600 6700 115500 115400 54500 54400 24000 23900 8700 8600 1100 1000 2700 2800 800 900 200 100 300 400 0 ...
output:
? 1 5000000 ? 1 5000001 ? 1 7500000 ? 1 7500001 ? 1 8750000 ? 1 8750001 ? 1 8125000 ? 1 8125001 ? 1 8437500 ? 1 8437501 ? 1 8281250 ? 1 8281251 ? 1 8203125 ? 1 8203126 ? 1 8164062 ? 1 8164063 ? 1 8144531 ? 1 8144532 ? 1 8154296 ? 1 8154297 ? 1 8159179 ? 1 8159180 ? 1 8156737 ? 1 8156738 ? 1 8155516 ...
result:
ok Solution answered 0 ans asked 47 questions
Test #7:
score: 0
Accepted
time: 0ms
memory: 3328kb
input:
1 10000000 90 244043825 244043846 259667601 259667552 234186909 234186902 234271163 234271166 233333663 233333666 233482703 233482700 233248328 233248325 233216474 233216477 233195535 233195536 233219033 233219030 233204384 233204381 233197061 233197058 233194314 233194315 233195231 233195228 233194...
output:
? 1 5000000 ? 1 5000001 ? 1 2500000 ? 1 2500001 ? 1 3750000 ? 1 3750001 ? 1 4375000 ? 1 4375001 ? 1 4062500 ? 1 4062501 ? 1 3906250 ? 1 3906251 ? 1 3984375 ? 1 3984376 ? 1 4023437 ? 1 4023438 ? 1 4003906 ? 1 4003907 ? 1 3994140 ? 1 3994141 ? 1 3999023 ? 1 3999024 ? 1 4001464 ? 1 4001465 ? 1 4002685 ...
result:
ok Solution answered 233194085 ans asked 47 questions
Test #8:
score: 0
Accepted
time: 0ms
memory: 3244kb
input:
1 10000000 90 253595644 253595664 268547024 268546988 241317318 241317314 242874378 242874390 240580594 240580596 240723514 240723512 240567264 240567262 240502468 240502470 240528202 240528200 240508672 240508670 240498906 240498904 240497584 240497586 240496466 240496464 240496362 240496364 240496...
output:
? 1 5000000 ? 1 5000001 ? 1 2500000 ? 1 2500001 ? 1 3750000 ? 1 3750001 ? 1 4375000 ? 1 4375001 ? 1 4062500 ? 1 4062501 ? 1 3906250 ? 1 3906251 ? 1 3984375 ? 1 3984376 ? 1 4023437 ? 1 4023438 ? 1 4003906 ? 1 4003907 ? 1 4013671 ? 1 4013672 ? 1 4018554 ? 1 4018555 ? 1 4020995 ? 1 4020996 ? 1 4019774 ...
result:
ok Solution answered 240496324 ans asked 49 questions
Test #9:
score: 0
Accepted
time: 6ms
memory: 3236kb
input:
1 6666666 90 141562892 141562905 188457341 188457292 157877022 157876997 147460347 147460322 142734644 142734625 141530103 141530096 141277240 141277243 141347816 141347809 141306385 141306382 141286855 141286852 141277090 141277087 141272356 141272359 141274648 141274645 141273427 141273424 1412728...
output:
? 1 3333333 ? 1 3333334 ? 1 1666666 ? 1 1666667 ? 1 2499999 ? 1 2500000 ? 1 2916666 ? 1 2916667 ? 1 3124999 ? 1 3125000 ? 1 3229166 ? 1 3229167 ? 1 3281249 ? 1 3281250 ? 1 3255207 ? 1 3255208 ? 1 3268228 ? 1 3268229 ? 1 3274738 ? 1 3274739 ? 1 3277993 ? 1 3277994 ? 1 3279621 ? 1 3279622 ? 1 3278807 ...
result:
ok Solution answered 141272281 ans asked 45 questions
Test #10:
score: 0
Accepted
time: 5ms
memory: 3268kb
input:
1 6666666 90 142487897 142487891 173370141 173370193 142819405 142819417 140825165 140825167 141237899 141237893 140616831 140616833 140925401 140925395 140769155 140769149 140691029 140691023 140651969 140651963 140632439 140632433 140622671 140622665 140617787 140617781 140616017 140616019 1406165...
output:
? 1 3333333 ? 1 3333334 ? 1 4999999 ? 1 5000000 ? 1 4166666 ? 1 4166667 ? 1 3749999 ? 1 3750000 ? 1 3541666 ? 1 3541667 ? 1 3645832 ? 1 3645833 ? 1 3593749 ? 1 3593750 ? 1 3619790 ? 1 3619791 ? 1 3632811 ? 1 3632812 ? 1 3639321 ? 1 3639322 ? 1 3642576 ? 1 3642577 ? 1 3644204 ? 1 3644205 ? 1 3645018 ...
result:
ok Solution answered 140615849 ans asked 47 questions
Subtask #3:
score: 5
Accepted
Test #11:
score: 5
Accepted
time: 7ms
memory: 3280kb
input:
10000000 10000000 170 680033200 680033300 680033100 180033200 180033300 180033100 69966800 69966700 69966900 55033200 55033300 55033100 48699000 48699100 48699100 17449000 17449100 17449100 7466800 7466700 7466900 1823900 1824000 1824000 2082300 2082200 2082200 345700 345800 345600 630900 630800 631...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 2500000 7500000 ? 2500001 7500000 ? 2500000 7500001 ? 1250000 8750000 ? 1250001 8750000 ? 1250000 8750001 ? 1875000 8125000 ? 1875001 8125000 ? 1875000 8125001 ? 1562500 8437500 ? 1562501 8437500 ? 1562500 8437501 ? 1406250 8281250 ? 1406251 82...
result:
ok Solution answered 0 ans asked 70 questions
Test #12:
score: 0
Accepted
time: 5ms
memory: 3272kb
input:
10000000 10000000 170 494067769 494067762 494067764 592655167 592655210 592655196 521168637 521168666 521168656 499962997 499963018 499963002 493798227 493798230 493798226 493791739 493791742 493791742 493322989 493322992 493322992 493190137 493190134 493190140 493093103 493093104 493093106 49307295...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 7500000 7500000 ? 7500001 7500000 ? 7500000 7500001 ? 6250000 6250000 ? 6250001 6250000 ? 6250000 6250001 ? 5625000 5625000 ? 5625001 5625000 ? 5625000 5625001 ? 5312500 5312500 ? 5312501 5312500 ? 5312500 5312501 ? 5156250 5468750 ? 5156251 54...
result:
ok Solution answered 493034338 ans asked 70 questions
Test #13:
score: 0
Accepted
time: 7ms
memory: 3184kb
input:
10000000 10000000 170 474633541 474633545 474633549 591978771 591978723 591978723 500192187 500192157 500192165 475489741 475489725 475489739 473055891 473055885 473055895 471748213 471748209 471748217 471367599 471367601 471367601 471309751 471309747 471309749 471294159 471294159 471294161 47127875...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 2500000 2500000 ? 2500001 2500000 ? 2500000 2500001 ? 3750000 3750000 ? 3750001 3750000 ? 3750000 3750001 ? 4375000 4375000 ? 4375001 4375000 ? 4375000 4375001 ? 4687500 4687500 ? 4687501 4687500 ? 4687500 4687501 ? 4843750 4531250 ? 4843751 45...
result:
ok Solution answered 471261661 ans asked 70 questions
Test #14:
score: 0
Accepted
time: 6ms
memory: 3328kb
input:
5000000 6666666 170 271791438 271791441 271791461 313493405 313493350 313493370 276587008 276586977 276587013 268761101 268761074 268761088 263717986 263717963 263717981 261854468 261854457 261854463 261233131 261233124 261233126 261177414 261177411 261177419 261083011 261083008 261083016 261112679 ...
output:
? 2500000 3333333 ? 2500001 3333333 ? 2500000 3333334 ? 1250000 1666666 ? 1250001 1666666 ? 1250000 1666667 ? 1875000 2499999 ? 1875001 2499999 ? 1875000 2500000 ? 2187500 2083332 ? 2187501 2083332 ? 2187500 2083333 ? 2343750 2291665 ? 2343751 2291665 ? 2343750 2291666 ? 2421875 2395832 ? 2421876 23...
result:
ok Solution answered 261074243 ans asked 69 questions
Test #15:
score: 0
Accepted
time: 5ms
memory: 3176kb
input:
5000000 6666666 170 292408922 292408910 292408904 321371486 321371538 321371512 284135972 284135984 284135976 283426704 283426700 283426696 282122912 282122916 282122916 282330812 282330816 282330804 282020464 282020460 282020456 281826948 281826944 281826948 281799108 281799104 281799100 281779224 ...
output:
? 2500000 3333333 ? 2500001 3333333 ? 2500000 3333334 ? 3750000 4999999 ? 3750001 4999999 ? 3750000 5000000 ? 3125000 4166666 ? 3125001 4166666 ? 3125000 4166667 ? 2812500 3749999 ? 2812501 3749999 ? 2812500 3750000 ? 2968750 3958332 ? 2968751 3958332 ? 2968750 3958333 ? 2890625 3854165 ? 2890626 38...
result:
ok Solution answered 281773788 ans asked 69 questions
Subtask #4:
score: 5
Accepted
Test #16:
score: 5
Accepted
time: 2ms
memory: 3240kb
input:
10000000 10000000 100 680033200 680033300 680033100 180033200 180033300 180033100 69966800 69966700 69966900 55033200 55033300 55033100 48699000 48699100 48699100 17449000 17449100 17449100 7466800 7466700 7466900 1823900 1824000 1824000 2082300 2082200 2082200 345700 345800 345600 630900 630800 631...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 2500000 7500000 ? 2500001 7500000 ? 2500000 7500001 ? 1250000 8750000 ? 1250001 8750000 ? 1250000 8750001 ? 1875000 8125000 ? 1875001 8125000 ? 1875000 8125001 ? 1562500 8437500 ? 1562501 8437500 ? 1562500 8437501 ? 1406250 8281250 ? 1406251 82...
result:
ok Solution answered 0 ans asked 70 questions
Test #17:
score: 0
Accepted
time: 0ms
memory: 3172kb
input:
10000000 10000000 100 494067769 494067762 494067764 592655167 592655210 592655196 521168637 521168666 521168656 499962997 499963018 499963002 493798227 493798230 493798226 493791739 493791742 493791742 493322989 493322992 493322992 493190137 493190134 493190140 493093103 493093104 493093106 49307295...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 7500000 7500000 ? 7500001 7500000 ? 7500000 7500001 ? 6250000 6250000 ? 6250001 6250000 ? 6250000 6250001 ? 5625000 5625000 ? 5625001 5625000 ? 5625000 5625001 ? 5312500 5312500 ? 5312501 5312500 ? 5312500 5312501 ? 5156250 5468750 ? 5156251 54...
result:
ok Solution answered 493034338 ans asked 70 questions
Test #18:
score: 0
Accepted
time: 8ms
memory: 3260kb
input:
10000000 10000000 100 474633541 474633545 474633549 591978771 591978723 591978723 500192187 500192157 500192165 475489741 475489725 475489739 473055891 473055885 473055895 471748213 471748209 471748217 471367599 471367601 471367601 471309751 471309747 471309749 471294159 471294159 471294161 47127875...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 2500000 2500000 ? 2500001 2500000 ? 2500000 2500001 ? 3750000 3750000 ? 3750001 3750000 ? 3750000 3750001 ? 4375000 4375000 ? 4375001 4375000 ? 4375000 4375001 ? 4687500 4687500 ? 4687501 4687500 ? 4687500 4687501 ? 4843750 4531250 ? 4843751 45...
result:
ok Solution answered 471261661 ans asked 70 questions
Test #19:
score: 0
Accepted
time: 1ms
memory: 3304kb
input:
5000000 6666666 100 271791438 271791441 271791461 313493405 313493350 313493370 276587008 276586977 276587013 268761101 268761074 268761088 263717986 263717963 263717981 261854468 261854457 261854463 261233131 261233124 261233126 261177414 261177411 261177419 261083011 261083008 261083016 261112679 ...
output:
? 2500000 3333333 ? 2500001 3333333 ? 2500000 3333334 ? 1250000 1666666 ? 1250001 1666666 ? 1250000 1666667 ? 1875000 2499999 ? 1875001 2499999 ? 1875000 2500000 ? 2187500 2083332 ? 2187501 2083332 ? 2187500 2083333 ? 2343750 2291665 ? 2343751 2291665 ? 2343750 2291666 ? 2421875 2395832 ? 2421876 23...
result:
ok Solution answered 261074243 ans asked 69 questions
Test #20:
score: 0
Accepted
time: 0ms
memory: 3304kb
input:
5000000 6666666 100 292408922 292408910 292408904 321371486 321371538 321371512 284135972 284135984 284135976 283426704 283426700 283426696 282122912 282122916 282122916 282330812 282330816 282330804 282020464 282020460 282020456 281826948 281826944 281826948 281799108 281799104 281799100 281779224 ...
output:
? 2500000 3333333 ? 2500001 3333333 ? 2500000 3333334 ? 3750000 4999999 ? 3750001 4999999 ? 3750000 5000000 ? 3125000 4166666 ? 3125001 4166666 ? 3125000 4166667 ? 2812500 3749999 ? 2812501 3749999 ? 2812500 3750000 ? 2968750 3958332 ? 2968751 3958332 ? 2968750 3958333 ? 2890625 3854165 ? 2890626 38...
result:
ok Solution answered 281773788 ans asked 69 questions
Subtask #5:
score: 5
Accepted
Test #21:
score: 5
Accepted
time: 0ms
memory: 3308kb
input:
10000000 10000000 75 680033200 680033300 680033100 180033200 180033300 180033100 69966800 69966700 69966900 55033200 55033300 55033100 48699000 48699100 48699100 17449000 17449100 17449100 7466800 7466700 7466900 1823900 1824000 1824000 2082300 2082200 2082200 345700 345800 345600 630900 630800 6310...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 2500000 7500000 ? 2500001 7500000 ? 2500000 7500001 ? 1250000 8750000 ? 1250001 8750000 ? 1250000 8750001 ? 1875000 8125000 ? 1875001 8125000 ? 1875000 8125001 ? 1562500 8437500 ? 1562501 8437500 ? 1562500 8437501 ? 1406250 8281250 ? 1406251 82...
result:
ok Solution answered 0 ans asked 70 questions
Test #22:
score: 0
Accepted
time: 7ms
memory: 3276kb
input:
10000000 10000000 75 494067769 494067762 494067764 592655167 592655210 592655196 521168637 521168666 521168656 499962997 499963018 499963002 493798227 493798230 493798226 493791739 493791742 493791742 493322989 493322992 493322992 493190137 493190134 493190140 493093103 493093104 493093106 493072951...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 7500000 7500000 ? 7500001 7500000 ? 7500000 7500001 ? 6250000 6250000 ? 6250001 6250000 ? 6250000 6250001 ? 5625000 5625000 ? 5625001 5625000 ? 5625000 5625001 ? 5312500 5312500 ? 5312501 5312500 ? 5312500 5312501 ? 5156250 5468750 ? 5156251 54...
result:
ok Solution answered 493034338 ans asked 70 questions
Test #23:
score: 0
Accepted
time: 2ms
memory: 3244kb
input:
10000000 10000000 75 474633541 474633545 474633549 591978771 591978723 591978723 500192187 500192157 500192165 475489741 475489725 475489739 473055891 473055885 473055895 471748213 471748209 471748217 471367599 471367601 471367601 471309751 471309747 471309749 471294159 471294159 471294161 471278751...
output:
? 5000000 5000000 ? 5000001 5000000 ? 5000000 5000001 ? 2500000 2500000 ? 2500001 2500000 ? 2500000 2500001 ? 3750000 3750000 ? 3750001 3750000 ? 3750000 3750001 ? 4375000 4375000 ? 4375001 4375000 ? 4375000 4375001 ? 4687500 4687500 ? 4687501 4687500 ? 4687500 4687501 ? 4843750 4531250 ? 4843751 45...
result:
ok Solution answered 471261661 ans asked 70 questions
Test #24:
score: 0
Accepted
time: 0ms
memory: 3168kb
input:
5000000 6666666 75 271791438 271791441 271791461 313493405 313493350 313493370 276587008 276586977 276587013 268761101 268761074 268761088 263717986 263717963 263717981 261854468 261854457 261854463 261233131 261233124 261233126 261177414 261177411 261177419 261083011 261083008 261083016 261112679 2...
output:
? 2500000 3333333 ? 2500001 3333333 ? 2500000 3333334 ? 1250000 1666666 ? 1250001 1666666 ? 1250000 1666667 ? 1875000 2499999 ? 1875001 2499999 ? 1875000 2500000 ? 2187500 2083332 ? 2187501 2083332 ? 2187500 2083333 ? 2343750 2291665 ? 2343751 2291665 ? 2343750 2291666 ? 2421875 2395832 ? 2421876 23...
result:
ok Solution answered 261074243 ans asked 69 questions
Test #25:
score: 0
Accepted
time: 7ms
memory: 3292kb
input:
5000000 6666666 75 292408922 292408910 292408904 321371486 321371538 321371512 284135972 284135984 284135976 283426704 283426700 283426696 282122912 282122916 282122916 282330812 282330816 282330804 282020464 282020460 282020456 281826948 281826944 281826948 281799108 281799104 281799100 281779224 2...
output:
? 2500000 3333333 ? 2500001 3333333 ? 2500000 3333334 ? 3750000 4999999 ? 3750001 4999999 ? 3750000 5000000 ? 3125000 4166666 ? 3125001 4166666 ? 3125000 4166667 ? 2812500 3749999 ? 2812501 3749999 ? 2812500 3750000 ? 2968750 3958332 ? 2968751 3958332 ? 2968750 3958333 ? 2890625 3854165 ? 2890626 38...
result:
ok Solution answered 281773788 ans asked 69 questions
Extra Test:
score: 0
Extra Test Passed