QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263100#7744. Elevatorucup-team1134#AC ✓62ms6860kbC++177.1kb2023-11-24 15:17:392023-11-24 15:17:41

Judging History

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

  • [2023-11-24 15:17:41]
  • 评测
  • 测评结果：AC
  • 用时：62ms
  • 内存：6860kb
查看
  • [2023-11-24 15:17:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

ll solve1(vector<pair<ll,ll>> A,vector<pair<ll,ll>> B,ll K){
    ll ans=0;
    
    sort(all(A));
    sort(all(B));
    
    reverse(all(A));
    reverse(all(B));
    
    int i=0,j=0;
    ll now=0;
    while(i<si(A)||j<si(B)){
        if(i==si(A)){
            if(now>=K-1) now=0;
            
            if(now){
                ll can=min((K-now)/2,B[j].se);
                now+=can*2;
                B[j].se-=can;
                
                if(now>=K-1) now=0;
                if(B[j].se==0) j++;
            }else{
                ll can=min((K-now)/2,B[j].se);
                ll tk=B[j].se/can;
                if(tk>=2){
                    ans+=B[j].fi*tk;
                    B[j].se-=can*tk;
                    if(B[j].se==0) j++;
                }else{
                    if(now==0) ans+=B[j].fi;
                    ll can=min((K-now)/2,B[j].se);
                    now+=can*2;
                    B[j].se-=can;
                    
                    if(now>=K-1) now=0;
                    if(B[j].se==0) j++;
                }
            }
        }else if(j==si(B)){
            if(now){
                ll can=min((K-now),A[i].se);
                now+=can;
                A[i].se-=can;
                
                if(now>=K) now=0;
                if(A[i].se==0) i++;
            }else{
                ll can=min(K-now,A[i].se);
                ll tk=A[i].se/can;
                if(tk>=2){
                    ans+=A[i].fi*tk;
                    A[i].se-=can*tk;
                    if(A[i].se==0) i++;
                }else{
                    if(now==0) ans+=A[i].fi;
                    ll can=min(K-now,A[i].se);
                    now+=can;
                    A[i].se-=can;
                    
                    if(now>=K) now=0;
                    if(A[i].se==0) i++;
                }
            }
        }else if(now==K-1){
            if(now==0) ans+=A[i].fi;
            ll can=min(K-now,A[i].se);
            now+=can;
            A[i].se-=can;
            
            if(now>=K) now=0;
            if(A[i].se==0) i++;
        }else if(A[i].fi<=B[j].fi){
            if(now>=K-1) now=0;
            
            if(now){
                ll can=min((K-now)/2,B[j].se);
                now+=can*2;
                B[j].se-=can;
                
                if(now>=K) now=0;
                if(B[j].se==0) j++;
            }else{
                ll can=min((K-now)/2,B[j].se);
                ll tk=B[j].se/can;
                if(tk>=2){
                    ans+=B[j].fi*tk;
                    B[j].se-=can*tk;
                    if(B[j].se==0) j++;
                }else{
                    if(now==0) ans+=B[j].fi;
                    ll can=min((K-now)/2,B[j].se);
                    now+=can*2;
                    B[j].se-=can;
                    
                    if(now>=K) now=0;
                    if(B[j].se==0) j++;
                }
            }
        }else{
            if(now){
                ll can=min((K-now),A[i].se);
                now+=can;
                A[i].se-=can;
                
                if(now>=K) now=0;
                if(A[i].se==0) i++;
            }else{
                ll can=min(K-now,A[i].se);
                ll tk=A[i].se/can;
                if(tk>=2){
                    ans+=A[i].fi*tk;
                    A[i].se-=can*tk;
                    if(A[i].se==0) i++;
                }else{
                    if(now==0) ans+=A[i].fi;
                    ll can=min(K-now,A[i].se);
                    now+=can;
                    A[i].se-=can;
                    
                    if(now>=K) now=0;
                    if(A[i].se==0) i++;
                }
            }
        }
        
        //cout<<i<<" "<<j<<" "<<now<<" "<<ans<<endl;
    }
    
    return ans;
}

ll solve2(vector<pair<ll,ll>> A,vector<pair<ll,ll>> B,ll K){
    ll ans=0;
    
    sort(all(A));
    sort(all(B));
    
    reverse(all(A));
    reverse(all(B));
    
    int i=0,j=0;
    ll now=0;
    while(i<si(A)||j<si(B)){
        if(i==si(A)){
            if(now==0) ans+=B[j].fi;
            ll can=min((K-now)/2,B[j].se);
            now+=can*2;
            B[j].se-=can;
            
            if(now>=K-1) now=0;
            if(B[j].se==0) j++;
        }else if(j==si(B)){
            if(now==0) ans+=A[i].fi;
            ll can=min(K-now,A[i].se);
            now+=can;
            A[i].se-=can;
            
            if(now>=K) now=0;
            if(A[i].se==0) i++;
        }else if(now==K-1){
            if(now==0) ans+=A[i].fi;
            ll can=min(K-now,A[i].se);
            now+=can;
            A[i].se-=can;
            
            if(now>=K) now=0;
            if(A[i].se==0) i++;
        }else if(A[i].fi<=B[j].fi){
            if(now==0) ans+=B[j].fi;
            ll can=min((K-now)/2,B[j].se);
            now+=can*2;
            B[j].se-=can;
            
            if(now>=K) now=0;
            if(B[j].se==0) j++;
        }else{
            if(now==0) ans+=A[i].fi;
            ll can=min(K-now,A[i].se);
            now+=can;
            A[i].se-=can;
            
            if(now>=K) now=0;
            if(A[i].se==0) i++;
        }
        
        //cout<<i<<" "<<j<<" "<<now<<" "<<ans<<endl;
    }
    
    return ans;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    /*
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ll q=0;
    while(1){
        int N=rng()%100+1;
        ll K=rng()%100+1;
        K*=2;
        
        vector<pair<ll,ll>> A,B;
        
        for(int q=0;q<N;q++){
            ll a,b,c;
            b=rng()%2+1;
            a=rng()%1000+1;
            c=rng()%1000+1;
            if(b==1) A.push_back(mp(c,a));
            else B.push_back(mp(c,a));
        }
        
        ll x=solve1(A,B,K),y=solve2(A,B,K);
        
        if(x!=y){
            cout<<x<<" "<<y<<endl;
            cout<<K<<endl;
            for(auto [a,b]:A) cout<<'A'<<" "<<a<<" "<<b<<endl;
            for(auto [a,b]:B) cout<<'B'<<" "<<a<<" "<<b<<endl;
            return 0;
        }
        
        q++;
        if(q%10000==0) cout<<q<<endl;
    }
     */
    int Q;cin>>Q;
    while(Q--){
        ll N,K;cin>>N>>K;
        vector<pair<ll,ll>> A,B;
        ll ans=0;
        for(int i=0;i<N;i++){
            ll a,b,c;cin>>a>>b>>c;
            if(b==1) A.push_back(mp(c,a));
            else B.push_back(mp(c,a));
        }
        cout<<solve1(A,B,K)<<"\n";
    }
}
Source code, Language: C++17

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 38ms
memory: 6220kb

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
17
6
4
1
8
5
5
7
1
3
23
6
3
3
2
2
2
3
8
1
5
6
9
11
147
7
10
2
7
7
8
6
5
5
1
7
3
5
10
7
7
10
8
1
4
2
3
9
1
5
2
9
1
6
7
7
6
10
18
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
21
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:

ok 5501 lines

Test #3:

score: 0
Accepted
time: 62ms
memory: 6860kb

input:

3
100000 8
8 2 6
7 2 8
5 1 10
7 2 7
4 1 7
6 2 9
7 1 2
3 1 1
5 1 10
5 1 1
3 2 10
5 2 5
7 1 6
5 2 7
7 2 1
5 1 6
2 2 10
8 1 7
7 1 1
10 2 6
9 1 1
8 1 4
10 1 4
6 1 1
4 1 4
1 2 9
3 2 6
6 1 3
4 1 7
9 2 5
8 2 4
7 2 1
2 2 10
6 2 9
3 1 3
2 2 3
2 2 4
7 2 4
8 1 1
5 2 3
5 2 7
7 2 9
1 1 4
5 1 2
2 1 9
3 2 1
9 2 2
...

output:

568601
4708350936
93900404329230

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 54ms
memory: 6504kb

input:

3
100000 174
90429 1 64237
30851 1 44358
63571 2 89174
20391 2 28747
13561 2 88689
81508 2 28383
85733 1 5777
37524 2 34730
10588 2 88519
61493 2 83682
55885 1 65270
17669 2 63015
85387 1 64757
91420 2 74020
9067 2 91750
20809 1 52771
36478 2 17941
62064 1 36433
72912 2 6100
53923 2 73971
65825 2 39...

output:

2156004461915
884586357480
59034901233

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 44ms
memory: 6752kb

input:

3
100000 4418822
19907 1 13081
59730 2 93611
35050 1 5867
87777 1 21890
18374 1 82418
79526 2 76106
33510 2 45826
75573 1 42240
35449 1 98727
80720 2 65290
32021 2 51348
52399 2 97828
75498 2 51728
89905 1 22825
2855 1 26204
11427 1 99583
55530 2 37895
22256 2 92230
19533 1 9142
16138 1 54018
53102 ...

output:

84699074
270668
100000

result:

ok 3 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-02 21:40:56 | OpenSource Project