QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554486#8553. Exchanging Kubicucup-team1231#RE 0ms3780kbC++142.9kb2024-09-09 11:30:292024-09-09 11:30:30

Judging History

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

  • [2024-09-09 11:30:30]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3780kb
  • [2024-09-09 11:30:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const LL INF = (LL)1e15;

LL query(int l, int r) {
    printf("? %d %d\n", l, r);
    fflush(stdout);
    LL ret;
    scanf("%lld", &ret);
    return ret;
}
vector<LL> calc(vector<pair<LL, PII> > seq) {
    // for(auto i : seq) printf("(%lld, %d:%d) ", i.first, i.second.first, i.second.second); printf("\n");
    if(seq.size() == 1) return vector<LL>();

    pair<LL, int> mn = make_pair(INF, -1);
    for(int i = 0; i < (int)seq.size(); i++)
        mn = min(mn, make_pair(seq[i].first, i));

    LL mv = mn.first; 
    int mp = mn.second;
    LL tl = mp > 0 ? query(seq[mp - 1].second.first, seq[mp].second.second)
    - seq[mp - 1].first: 0, tr = mp < (int)seq.size() - 1 ?
    query(seq[mp].second.first, seq[mp + 1].second.second) - seq[mp + 1].first : 0;
    
    if(tr == 0 && tl > 0) {
        tr = tl + seq[mp - 1].first; mp--;
    } else if(tr > 0) tr += seq[mp + 1].first;
    // printf("%d %lld\n", mp, tr);
    if(tr > 0) {
        LL neg = tr - seq[mp].first - seq[mp + 1].first;
        seq[mp + 1] = make_pair(tr, make_pair(seq[mp].second.first, seq[mp + 1].second.second));
        // printf("good %lld\n", neg);
        seq.erase(seq.begin() + mp);
        vector<LL> ret = calc(seq);
        ret.insert(ret.begin() + mp, neg);
        // for(auto i : ret) printf("[%lld] ", i); printf("\n");
        return ret;
    } {
        LL pos = seq[mp].first;
        // printf("bad %lld\n", pos);
        seq.erase(seq.begin() + mp);
        vector<LL> ret = calc(seq);
        if(mp == 0) ret.insert(ret.begin(), -pos);
        else if(mp == (int)seq.size()) ret.insert(ret.end(), -pos);
        else {
            assert(ret[mp - 1] <= -pos);
            ret.insert(ret.begin() + mp, -pos);
        }
        // for(auto i : ret) printf("[%lld] ", i); printf("\n");
        return ret;
    }
    
    return vector<LL>();
}

int n;
LL a[2005];
void solve() {
    scanf("%d", &n);

    for(int i = 1; i <= n; i++) a[i] = query(i, i);
    
    int tl = -1, tr = -1;
    LL S = 0;
    vector<pair<LL, PII> > vec;
    vector<int> neg;
    for(int i = 1; i <= n; i++) {
        if(a[i] == 0) {
            if(tr != -1) {
                vec.push_back(make_pair(S, make_pair(tl, tr)));
                neg.push_back(i);
                S = 0;
            }
            tl = -1; tr = -1;
        } else {
            S += a[i];
            if(tl == -1) tl = i;
            tr = max(tr, i);
        }
    }
    if(tr != -1) vec.push_back(make_pair(S, make_pair(tl, tr)));
    
    vector<LL> ret = calc(vec);
    for(int i = 0; i < (int)ret.size(); i++) a[neg[i]] = ret[i];

    printf("!");
    for(int i = 1; i <= n; i++) printf(" %lld", a[i]);
    printf("\n");
    fflush(stdout);
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

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 -1 1
? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 1 3
? 1 5
! 2 -1 3 -4 5

result:

ok ok (2 test cases)

Test #2:

score: -100
Runtime Error

input:

10000
1
718876398
1
0

output:

? 1 1
! 718876398
? 1 1

result: