QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63524#2727. Gradient DescentBaltinic25 ✓8ms3328kbC++141.1kb2022-11-22 15:01:452022-11-22 15:01:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-22 15:01:47]
  • 评测
  • 测评结果:25
  • 用时:8ms
  • 内存:3328kb
  • [2022-11-22 15:01:45]
  • 提交

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