QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268832 | #7744. Elevator | 2986858916 | WA | 41ms | 3648kb | C++20 | 3.4kb | 2023-11-28 21:54:38 | 2023-11-28 21:54:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ll long long
#define lowbit(x) x&-x
const int N=1e7+1,mod=1e9+19;
void solve(){
int n,k;cin>>n>>k;
vector<pair<int,int>>a,b;
map<int,int>one,two;
for(int i=0;i<n;i++){
int c,w,f;cin>>c>>w>>f;
if(w==1){
one[f]+=c;
}else two[f]+=c;
// if(w==1)a.emplace_back(c,f);
// else b.emplace_back(c,f);
}
for(auto &[f,c]:one)a.emplace_back(c,f);
for(auto &[f,c]:two)b.emplace_back(c,f);
function<bool(pair<int,int>,pair<int,int>)>cmp=[&](const auto x,const auto y){
return x.second>y.second;
};
sort(a.begin(),a.end(),cmp);
sort(b.begin(),b.end(),cmp);
ll ans=0;
int p=k,cnt=0,ex=0;
int l=0,li=0;
while(l<a.size()||li<b.size()){
if(l<a.size()&&li<b.size()){
if(a[l].second>b[li].second){
if(a[l].first<=ex)ex-=a[l].first,a[l].first=0;
else a[l].first-=ex,ex=0;
if(p==k){
cnt=a[l].second;
}
if(a[l].first>=k){
ans+=1ll*a[l].first/k*a[l].second;
a[l].first=a[l].first%k;
}
if(p>=a[l].first)p-=a[l].first;
else p=a[l].first-p,ans+=cnt,cnt=a[l].second;
l++;
}else {
if(p==k){
cnt=b[li].second;
}
if(p==1){
ans+=cnt;
p=k;
ex++;
continue;
}
if(b[li].first>=k/2){
ans+=1l*b[li].first/(k/2)*b[li].second;
b[li].first=b[li].first%(k/2);
}
if(p>=b[li].first*2)p-=b[li].first*2;
else{
if(p&1)ex++;
p=b[li].first*2-p,ans+=cnt,cnt=b[li].second;
}li++;
}
}else if(l<a.size()){
if(a[l].first<=ex)ex-=a[l].first,a[l].first=0;
else a[l].first-=ex,ex=0;
if(p==k){
cnt=a[l].second;
}
if(a[l].first>=k){
ans+=1ll*a[l].first/k*a[l].second;
a[l].first=a[l].first%k;
}
if(p>=a[l].first)p-=a[l].first;
else p=a[l].first-p,ans+=cnt,cnt=a[l].second;
l++;
}else {
if(p==k){
cnt=b[li].second;
}
if(p==1){
ans+=cnt;
p=k;
ex++;
continue;
}
if(b[li].first>=k/2){
ans+=1ll*b[li].first/(k/2)*b[li].second;
b[li].first=b[li].first%(k/2);
}
if(p>=b[li].first*2)p-=b[li].first*2;
else {
if(p&1)ex++;
p=b[li].first*2-p,ans+=cnt,cnt=b[li].second;
}
li++;
}
if(p==0){
p=k;ans+=cnt;
}
}
if(p!=k)ans+=cnt;
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
2 4 6 1 1 8 7 2 5 1 1 7 3 2 6 8 1200000 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345
output:
24 100000
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 41ms
memory: 3648kb
input:
5501 8 104 5 2 3 6 2 4 5 2 3 6 2 9 8 2 4 2 1 3 7 2 4 8 2 8 1 290 3 1 1 12 12 6 1 2 1 2 2 1 1 2 1 2 4 6 1 1 1 2 5 6 1 4 4 1 4 6 2 4 6 2 5 4 2 5 4 1 4 5 334 1 1 4 1 2 3 4 2 1 5 1 1 2 1 2 13 218 5 2 3 5 1 4 1 2 1 1 2 5 3 2 2 1 1 3 4 2 2 1 2 5 2 2 1 2 1 5 3 2 1 5 2 1 1 1 4 10 260 7 2 1 5 1 1 5 2 4 6 1 6...
output:
9 1 23 4 5 7 1 3 9 6 1 10 4 9 20 6 4 1 8 5 5 7 1 3 35 6 3 3 2 2 2 3 8 1 6 6 9 11 147 7 10 2 7 7 8 6 5 5 1 7 4 5 10 7 7 10 8 1 4 2 3 9 1 5 2 9 1 6 7 7 6 10 34 8 10 4 10 9 2 8 3 5 9 3 6 5 3 2 6 1 3 2 2 1 6 9 6 3 4 8 9 9 2 6 1 2 6 7 5 2 5 26 8 1 2 3 4 9 3 4 6 5 9 6 1 7 3 7 3 2 2 8 7 3 5 9 7 10 7 3 2 4 ...
result:
wrong answer 15th lines differ - expected: '17', found: '20'