QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#393672	#7944. Max Minus Min	kyuukyuusha^#	WA	33ms	3876kb	C++17	2.1kb	2024-04-19 05:41:33	2024-04-19 05:41:33

Judging History

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

[2024-04-19 05:41:33]
评测

测评结果：WA
用时：33ms
内存：3876kb

查看

[2024-04-19 05:41:33]
提交

answer

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int tn = 1;
  cin >> tn;
  while (tn--) {
    int n;
    cin >> n;
    vector<int> a_(n);
    for (auto &x : a_) cin >> x;
    
    int conclusion = 1e9+5;
    for (int k : array<int,2>{1, -1}) {
      vector<int> a(n);
      for (int i = 0; i < n; ++i) a[i] = k * a_[i];
    
      vector<array<int, 2>> pairs(n);
      for (int i = 0; i < n; ++i) pairs[i] = {a[i], i};
      sort(pairs.begin(), pairs.end());
      const int hi = pairs.back()[0];  // max
      const int lo = pairs.front()[0]; // min
      int ans = hi - lo; // max - min (pick x=0 case)
      
      vector<pair<int, vector<int>>> idx; // <x, {i : a[i]=x}> aka <x, indices>
      for (auto [x, i] : pairs) {
        if (idx.empty() || idx.back().first != x) idx.push_back({x, {}});
        idx.back().second.push_back(i);
      }
      
      // for (auto [x, ia] : idx) {
      //   cout << x << " [";
      //   for (auto i : ia) cout << i << " ";
      //   cout << "\n";
      // }
      
      // increase the min, make sure don't touch max
      
      vector<array<int, 3>> minPU; // <x, l, r> prefix union
      for (int i = 0; i < idx.size(); ++i) {
        const auto& [x, ia] = idx[i];
        int L = ia.front();
        int R = ia.back();
        if (i == 0) {
          minPU.push_back({x, L, R});
        } else {
          const auto& [y, ja] = idx[i-1];
          int L0 = ja.front();
          int R0 = ja.back();
          minPU.push_back({x, min(L, L0), max(R, R0)});
        }
      }
      
      int j = minPU.size()-1;
      for (int i = idx.size()-1; i >= 0; --i) {
        const auto& [x, ia] = idx[i];
        for (int k : ia) { // hit check
          while (j >= 0 && minPU[j][1] <= k && k <= minPU[j][2]) --j;
        }
        if (j >= 0) { // calculate
          int candidate = max(minPU[j][0] - lo, hi - x);
          ans = min(ans, candidate);
        } else break; // failed
      }
      conclusion = min(conclusion, ans);
    }
    
    cout << conclusion;
    cout << endl;
  }
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3876kb

input:

4
3
42 42 42
4
1 2 2 1
5
1 100 1 100 1
6
1 2 3 4 5 6

output:

result:

ok 4 number(s): "0 0 99 2"

Test #2:

score: -100

Wrong Answer

time: 33ms

memory: 3564kb

input:

19530
6
2 3 3 3 4 3
6
2 4 4 2 5 5
6
2 5 2 5 1 3
6
4 4 1 2 4 1
5
5 4 5 3 3
5
2 2 1 5 1
6
3 1 2 4 2 3
5
5 5 4 4 5
6
5 3 3 1 4 2
6
3 3 2 4 2 4
6
1 2 4 5 2 5
5
3 4 5 5 3
6
4 3 3 3 4 3
6
1 5 1 2 3 1
5
5 5 2 1 4
6
1 2 5 3 5 2
6
4 5 2 4 5 2
5
2 4 2 4 1
4
2 3 3 3
6
1 2 2 1 4 5
6
3 2 1 3 3 2
6
2 1 1 2 5 3
6
...

output:

result:

wrong answer 1st numbers differ - expected: '1', found: '0'