QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388640#8553. Exchanging Kubicucup-team1198#AC ✓34ms3896kbC++205.0kb2024-04-13 17:46:402024-04-13 17:46:40

Judging History

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

  • [2024-04-13 17:46:40]
  • 评测
  • 测评结果:AC
  • 用时:34ms
  • 内存:3896kb
  • [2024-04-13 17:46:40]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define int long long

const int inf = 1e15;

int n;
vector<int> a_test;

void gen_test() {
    n = rand() % 50 + 1;
    a_test.resize(n);
    for (int i = 0; i < n; ++i) {
        a_test[i] = rand() % 100 - 50;
    }
}

int get(int l, int r, vector<int>& a) {
    int res = 0;
    for (int i = l; i < r; ++i) {
        int sum = 0;
        for (int j = i; j < r; ++j) {
            sum += a[j];
            res = max(res, sum);
        }
    }
    return res;
}

int ask(int l, int r) {
    // return get(l, r, a_test);

    cout << "? " << l + 1 << ' ' << r << endl;
    int res;
    cin >> res;
    return res;
}

struct Block {
    int l;
    int r;
    int sum;
};

void check(vector<int> ans) {
    // cerr << "check:\n";
    // cerr << "give = ";
    // for (int i : ans) cerr << i << ' ';
    // cerr << '\n';

    // cerr << "need = ";
    // for (int i : a_test) cerr << i << ' ';
    // cerr << '\n';

    // for (int l = 0; l < n; ++l) {
    //     for (int r = l + 1; r <= n; ++r) {
    //         assert(get(l, r, ans) == get(l, r, a_test));
    //     }
    // }

    cout << "! ";
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

void solve() {
    gen_test();
    cin >> n;

    vector<Block> b;
    vector<int> ans(n, 0);

    for (int i = 0; i < n; ++i) {
        ans[i] = ask(i, i + 1);
        if (ans[i] > 0) {
            int s = ans[i];
            for (int j = i + 1; j <= n; ++j) {
                if (j != n) ans[j] = ask(j, j + 1);
                if (j == n || ans[j] == 0) {
                    // stop
                    b.push_back(Block{i, j, s});
                    i = j;
                    break;
                } else {
                    s += ans[j];
                }
            }
        } else {
            continue;
        }
    }

    while (b.size() >= 2) {
        // cerr << "blocks:\n";
        // for (auto bb : b) {
        //     cerr << bb.l << ' ' << bb.r << ' ' << bb.sum << ",   ";
        // }
        // cerr << '\n';

        if (b[0].sum <= b[1].sum) {
            int r = ask(b[0].l, b[1].r);
            if (r == b[1].sum) {
                ans[b[0].r] = -inf;
                b.erase(b.begin());
            } else {
                ans[b[0].r] = - (b[0].sum + b[1].sum - r);

                auto l0 = b[0].l;
                auto r1 = b[1].r;
                b.erase(b.begin(), b.begin() + 2);
                b.insert(b.begin(), Block(l0, r1, r));
            }
        } else if (b[b.size() - 1].sum <= b[b.size() - 2].sum) {
            int r = ask(b[b.size() - 2].l, b[b.size() - 1].r);
            if (r == b[b.size() - 2].sum) {
                ans[b[b.size() - 2].r] = -inf;
                b.erase(--b.end());
            } else {
                ans[b[b.size() - 2].r] = - (b[b.size() - 2].sum + b[b.size() - 1].sum - r);

                auto l0 = b[b.size() - 2].l;
                auto r1 = b[b.size() - 1].r;
                b.pop_back();
                b.pop_back();
                b.insert(b.end(), Block(l0, r1, r));
            }
        } else {
            for (int i = 0; i + 2 < b.size(); ++i) {
                if (b[i].sum >= b[i + 1].sum && b[i + 1].sum <= b[i + 2].sum) {
                    int rl = ask(b[i].l, b[i + 1].r);
                    if (rl == b[i].sum) {
                        int rr = ask(b[i + 1].l, b[i + 2].r);
                        if (rr == b[i + 2].sum) {
                            // hmm
                            ans[b[i + 1].r] = -b[i + 1].sum;
                            b.erase(b.begin() + i + 1);
                        } else {
                            ans[b[i + 1].r] = -(b[i + 1].sum + b[i + 2].sum - rr);
                            auto l0 = b[i + 1].l;
                            auto r1 = b[i + 2].r;
                            b.erase(b.begin() + i + 1, b.begin() + i + 3);
                            b.insert(b.begin() + i + 1, Block(l0, r1, rr));
                        }
                    } else {
                        ans[b[i].r] = -(b[i].sum + b[i + 1].sum - rl);
                        auto l0 = b[i].l;
                        auto r1 = b[i + 1].r;
                        b.erase(b.begin() + i, b.begin() + i + 2);
                        b.insert(b.begin() + i, Block(l0, r1, rl));
                    }
                    break;
                }
            }
        }
    }

    check(ans);
    // cerr << "ok\n\n\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 10000;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

2
3
1
0
1
1
5
2
0
3
0
5
4
5

output:

? 1 1
? 2 2
? 3 3
? 1 3
! 1 -1000000000000000 1 
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 1 3
? 1 5
! 2 -1 3 -1000000000000000 5 

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 9ms
memory: 3632kb

input:

10000
1
718876398
1
0
1
0
1
0
1
938356223
1
857157125
1
0
1
0
1
0
1
0
1
0
1
965894497
1
0
1
626061677
1
642094813
1
107398046
1
0
1
0
1
0
1
287188651
1
0
1
345108193
1
0
1
0
1
714952783
1
0
1
325760098
1
0
1
800487422
1
322806679
1
0
1
0
1
0
1
866952779
1
741483102
1
492063609
1
0
1
833448280
1
0
1
...

output:

? 1 1
! 718876398 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 938356223 
? 1 1
! 857157125 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 965894497 
? 1 1
! 0 
? 1 1
! 626061677 
? 1 1
! 642094813 
? 1 1
! 107398046 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 0 
? 1 1
! 287188651 
? 1 1
! 0 
? 1 1...

result:

ok ok (10000 test cases)

Test #3:

score: 0
Accepted
time: 4ms
memory: 3796kb

input:

1052
9
167536100
0
373372185
0
427949326
442758705
102715118
0
0
373372185
973423149
9
248442934
306962195
570791475
593033322
0
582850731
559429390
0
120053133
1142280121
2780526396
10
785691778
0
981032824
0
0
592503870
0
0
0
0
981032824
1112480382
10
0
737563509
985502704
427600980
0
805973591
77...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3
? 3 7
! 167536100 -1000000000000000 373372185 -1000000000000000 427949326 442758705 102715118 0 0 
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 6 9
? 1 7
! 248442934 306962195 570791475 593033322 -80983651 582850731 559429390 -10...

result:

ok ok (1052 test cases)

Test #4:

score: 0
Accepted
time: 17ms
memory: 3880kb

input:

105
98
0
622130364
0
603542943
491665548
0
535594695
169182905
269002770
437838930
534070706
783210752
0
914335037
560159875
0
216552904
666995724
0
0
0
753649796
0
0
0
779352417
0
121063647
0
496743470
0
4104890
0
648149367
0
965790695
732089017
0
0
0
0
6701195
0
0
0
0
750231085
0
0
511641740
36964...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (105 test cases)

Test #5:

score: 0
Accepted
time: 4ms
memory: 3824kb

input:

10
911
0
0
318490282
367703800
0
447141340
683983129
0
319014522
385248618
0
0
0
453686281
0
0
503449442
0
451161866
0
422033116
892391115
0
0
0
0
0
0
116949378
0
305018897
441460055
390798833
643328028
0
0
785497871
0
0
0
0
702685168
0
177748037
150437291
920782161
719254975
0
519494673
555035366
0...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (10 test cases)

Test #6:

score: 0
Accepted
time: 11ms
memory: 3884kb

input:

5
1952
0
207059033
0
846665449
247683562
650126777
348616690
570194875
727419904
504212241
0
0
491140658
0
876684021
0
8207113
0
0
0
0
0
0
325502144
0
78879155
0
828506541
357830073
0
831431906
864603826
0
0
656125431
582335892
651256373
0
640787570
0
103421615
0
0
0
0
0
481682299
493673601
93577949...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (5 test cases)

Test #7:

score: 0
Accepted
time: 22ms
memory: 3708kb

input:

5
2000
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (5 test cases)

Test #8:

score: 0
Accepted
time: 10ms
memory: 3860kb

input:

1052
9
911133045
0
526984535
0
931320524
0
928006811
0
176872302
928006811
1340686664
1331374524
1808307998
9
916585987
0
423565782
0
615681673
0
935399347
0
661248049
935399347
1275831339
1377399889
2278784416
10
587217915
0
129148010
0
316225345
0
935126806
0
641901481
0
935126806
587217915
316225...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 7 9
? 5 7
? 1 3
? 1 7
! 911133045 -106743056 526984535 -863753190 931320524 -518640671 928006811 -1000000000000000 176872302 
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 7 9
? 1 3
? 1 5
? 1 7
! 916585987 -64320430 423565782 -5141131...

result:

ok ok (1052 test cases)

Test #9:

score: 0
Accepted
time: 25ms
memory: 3644kb

input:

105
98
488529703
0
468492922
0
802901522
0
475641005
0
635144928
0
319324280
0
312095441
0
637285947
0
863514749
0
567178596
0
785897142
0
706104708
0
913552861
0
580235462
0
86293259
0
945400504
0
549373433
0
807677852
0
115856051
0
376484061
0
984127422
0
202884700
0
516705542
0
286842060
0
517315...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (105 test cases)

Test #10:

score: 0
Accepted
time: 13ms
memory: 3896kb

input:

10
911
190008868
0
267501671
0
615470163
0
133513401
0
314315377
0
660548519
0
555314918
0
941289689
0
231059371
0
56848945
0
294509086
0
423676574
0
947717893
0
631853488
0
420480249
0
447345907
0
368504182
0
757380250
0
498988264
0
155354017
0
832730679
0
982153581
0
779911649
0
228619121
0
524075...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (10 test cases)

Test #11:

score: 0
Accepted
time: 34ms
memory: 3880kb

input:

5
1952
270943944
0
427827622
0
706467567
0
657378898
0
336632977
0
646373280
0
330175227
0
636169757
0
614552419
0
752377204
0
964998361
0
223064174
0
402544250
0
855778411
0
374152994
0
278416329
0
988879952
0
151167996
0
775855140
0
366009963
0
63772275
0
189944036
0
123776551
0
636001304
0
860458...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 10 10
? 11 11
? 12 12
? 13 13
? 14 14
? 15 15
? 16 16
? 17 17
? 18 18
? 19 19
? 20 20
? 21 21
? 22 22
? 23 23
? 24 24
? 25 25
? 26 26
? 27 27
? 28 28
? 29 29
? 30 30
? 31 31
? 32 32
? 33 33
? 34 34
? 35 35
? 36 36
? 37 37
? 38 38
? 39 39
? 40 4...

result:

ok ok (5 test cases)

Extra Test:

score: 0
Extra Test Passed