QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671471 | #6695. Matching | Schoolbag | RE | 0ms | 3536kb | C++20 | 2.3kb | 2024-10-24 12:43:42 | 2024-10-24 12:43:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vc;
typedef vector<long long> vl;
typedef vector<vector<long long>> vll;
typedef __int128_t int128;
#define rep(x, y, z) for(int x = (y); x <= (z); x++)
#define per(x, y ,z) for(int x = (y); x >= (z); x--)
#define yes cout << "Yes\n"
#define no cout << "No\n"
//#define int long long
//const int N = 1e5 + 5;
//const int mod = 1e9 + 7;
const int inf = -1e9 - 5;
struct dsu{
vi fa, siz;
void init(int n){ // 初始化
fa.resize(n + 1);
iota(fa.begin(), fa.end(), 0);
siz.resize(n + 1, 1);
}
int find(int x){
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return;
if(siz[x] > siz[y]) swap(x, y);
fa[x] = y, siz[y] += siz[x];
return;
}
}d;
void solve(){
int n; cin >> n;
d.init(n);
vector<pii> p(n + 1, {-1, -1});
rep(i, 1, n){
cin >> p[i].first;
p[i].second = p[i].first - i;
}
sort(p.begin() + 1, p.end(), [&](pii x, pii y){
return x.second < y.second;
});
rep(i, 1, n){
int r = i;
while(p[i].second == p[r].second) r++;
r--;
rep(j, i, r){
d.merge(i, j);
}
i = r;
}
map<int, vi> mp;
rep(i, 1, n){
int fa = d.find(i);
mp[fa].push_back(p[i].first);
}
ll ans = 0;
for(auto [x, y] : mp){
sort(y.begin(), y.end(), [&](int x, int y){
return x > y;
});
int leny = y.size();
for(int i = 0; i < leny; i += 2){
if(i + 1 < leny){
if(y[i] + y[i+1] > 0){
ans += y[i] + y[i+1];
}
else break;
}
}
}
cout << ans << '\n';
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int __ = 1; cin >> __;
while(__--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
3 9 3 -5 5 6 7 -1 9 1 2 3 -5 -4 -3 3 1 10 100
output:
30 0 0
result:
ok 3 number(s): "30 0 0"
Test #2:
score: -100
Runtime Error
input:
5504 9 -1 -7 -6 -5 -4 -3 5 -1 0 5 999999995 999999993 999999995 999999995 999999995 5 3 -6 -5 -4 -2 4 -8 2 3 -5 4 -2 -1 0 1 9 -4 -9 3 -1 -1 -5 2 -3 -5 7 -1 -2 1 2 3 4 3 4 -2 5 2 -4 10 2 4 1 -3 -2 4 5 -3 0 -4 6 -1 0 1 2 4 -3 5 -4 -3 -2 -1 0 4 -1 0 1 2 8 1 0 -4 -1 0 -5 -3 -5 2 5 6 8 -4 -3 -2 -1 0 1 2 ...