QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554486 | #8553. Exchanging Kubic | ucup-team1231# | RE | 0ms | 3780kb | C++14 | 2.9kb | 2024-09-09 11:30:29 | 2024-09-09 11:30:30 |
Judging History
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