QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466071#8553. Exchanging KubiczlxFTHWA 28ms3832kbC++141.9kb2024-07-07 15:32:582024-07-07 15:32:58

Judging History

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

  • [2024-07-07 15:32:58]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:3832kb
  • [2024-07-07 15:32:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 2005;

LL ask(int l, int r) {
  cout << "? " << l << " " << r << endl;
  LL v;
  cin >> v;
  return v;
}

int n;
LL a[N];

void ouf() {
  cout << "!";
  for (int i = 1; i <= n; ++i) cout << " " << a[i];
  cout << endl;
}

struct Node {
  mutable int l, r;
  mutable LL v;
  Node(int l, int r, LL v) : l(l), r(r), v(v) {}
  bool operator<(const Node &rhs) const {
    return l < rhs.l;
  }
};

void solve() {
  cin >> n;
  fill(a + 1, a + n + 1, 0);
  set<Node> s;
  for (int i = 1; i <= n; ++i) {
    a[i] = ask(i, i);
    if (a[i] <= 0) continue;
    if (i > 1 && a[i - 1] > 0) {
      s.rbegin()->r = i;
      s.rbegin()->v += a[i];
    } else {
      s.emplace(i, i, a[i]);
    }
  }
  if (!s.size()) return ouf();
  auto qs = [&](int l, int r) {
    return accumulate(a + l, a + r + 1, 0ll);
  };
  while (s.size()) {
    auto p = s.end();
    for (auto it = s.begin(); it != s.end(); ++it)
      if (p == s.end() || it->v < p->v) p = it;
    if (p != s.begin()) {
      auto i = prev(p);
      auto val = ask(i->l, p->r);
      if (val > i->v) {
        a[p->l - 1] = val - i->v - p->v - qs(i->r + 1, p->l - 1);
        Node nw(i->l, p->r, val);
        s.erase(i), s.erase(p), s.insert(nw);
        continue;
      } else {
        a[p->l - 1] = -p->v;
      }
    }
    if (next(p) != s.end()) {
      auto i = next(p);
      auto val = ask(p->l, i->r);
      if (val > i->v) {
        a[p->r + 1] = val - i->v - p->v - qs(p->r + 1, i->l - 1);
        Node nw(p->l, i->r, val);
        s.erase(i), s.erase(p), s.insert(nw);
        continue;
      } else {
        a[p->r + 1] = -p->v;
      }
    }
    s.erase(p);
  }
  ouf();
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

详细

Test #1:

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

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: 0
Accepted
time: 28ms
memory: 3788kb

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
! 345108193
? 1 1
! ...

result:

ok ok (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3808kb

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
1112480382
1112480382
10
0
737563509
985502704
427600980
0
805973591
7...

output:

? 1 1
? 2 2
? 3 3
? 4 4
? 5 5
? 6 6
? 7 7
? 8 8
? 9 9
? 1 3
? 3 7
! 167536100 -167536100 373372185 -373372185 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 -120053133 1200531...

result:

wrong answer mss of [1, 4] is incorrect, expected=1670744515, found=2234086166 (test case 5)