oj.uz

Submission #1041673

# Submission time Handle Problem Language Result Execution time Memory
1041673 2024-08-02T06:56:54 Z vjudge1 Segway (COI19_segway) C++17
100 / 100
 271 ms 3224 KB 
//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define vb vector<bool>
#define vv vector<vi>
#define vp vector<pi>
#define vs vector<string>
#define ul map<int,vi>
#define ub map<int,bool>
#define ui map<int,int>
#define sum(a) accumulate(all(a),0)
#define add insert
// #define endl '\n' 
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
const int INF=1e18;
bool comp(vi &a, vi &b)
{
    return a[1]<b[1];
}

void solve()
{
    int n,k,e,m,ans=0;
    cin>>n;
    vv a(n+1);
    //rep(n){cin>>e;a.append(e);}
    rep(n)
    {
        cin>>k>>e>>m;
        a[i+1]={k,e,m};
    }
    vector<vector<int>> riders;
    rep(n)
    {
        // time , initial pos , distance, remaining nitro
        riders.append({0,i+1,0,0});
    }
    cin>>m;
    vi check;
    rep(m)
    {
        cin>>e;
        // cout<<e<<endl;
        check.append(e);
    }
    check.append(300);
    int distance=0;
    int isp=0; 
    for (int nitro_base : check)
    {
        // cout<<"nitro_base >> "<<nitro_base<<endl;ln;
        while  ( (( nitro_base + 99 ) / 100 ) * 100 > ( (isp + 1) * 100))
        {
            isp++;
            int to_travel = (isp)*100 - distance;
            // cout<< to_travel <<" "<< distance <<" >>>> while "<< (isp)*100 ;ln;
            for (auto & rider : riders)
            {
                // cout<<  "next"<<endl;
                // cout<<rider[0]<<" "<<rider[1]<<" "<<rider[2]<<" "<<rider[3];ln;
                // cout<<rider[3]<< " "<< to_travel;ln;
                rider[2]+=min(rider[3],to_travel);
                rider[0]+=min(rider[3],to_travel);
                rider[3]-=min(rider[3],to_travel);
                // cout<<rider[0]<<" "<<rider[1]<<" "<<rider[2]<<" "<<rider[3];ln;
                rider[0]+= ((isp)*100 - rider[2])* a[rider[1]][isp-1];
                rider[2]=(isp)*100;
                // cout<<rider[0]<<" "<<rider[1]<<" "<<rider[2]<<" "<<rider[3];ln;
            }
            distance=(isp)*100;
        }
        if ( (( nitro_base + 99 ) / 100 ) * 100 == ( (isp + 1) * 100))
        {
            int to_travel = nitro_base - distance;
            // cout<<nitro_base<<" "<<distance;ln;
            // cout<< to_travel <<" "<< distance <<" >>>>  for "<< nitro_base;ln;
            for (auto & rider : riders)
            {
                // cout<<rider[0]<<" "<<rider[1]<<" "<<rider[2]<<" "<<rider[3];ln;
                rider[2]+=min(rider[3],to_travel);
                rider[0]+=min(rider[3],to_travel);
                // cout<<rider[3]<< " "<< to_travel;ln;
                // cout<<min(rider[3],to_travel);ln;
                rider[3]-=min(rider[3],to_travel);
                rider[0]+= (nitro_base - rider[2])* a[rider[1]][isp];
                rider[2]=nitro_base;
                // cout<<rider[0]<<" "<<rider[1]<<" "<<rider[2]<<" "<<rider[3];ln;
            }
            distance =nitro_base;
            sort(all(riders));
            int pos=0;
            k=0;
            for (int i=1;i<n;i++)
            {
                if (riders[i][0]>riders[i-1][0])
                {
                    pos++;
                    pos+=k;
                    k=0;
                }
                else k++;
                // cout<<riders[i][3]<<endl;
                if (riders[i][3]==0)
                    riders[i][3]+=pos%20;
                // cout<<riders[i][3]<<endl;
            }
            
        }
        // cout<<distance<<endl;
    }

    sort(all(riders),comp);
    

    for (auto i: riders){cout<<i[0]<<"\n";}



// cout<<ans;
    // cout<<a.size();
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    while(ans--){
        // cout << "Case #" << ans << ": \n";
        solve();}}

Compilation message

segway.cpp: In function 'void solve()':
segway.cpp:51:17: warning: unused variable 'ans' [-Wunused-variable]
   51 |     int n,k,e,m,ans=0;
      |                 ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 14 ms 3224 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 408 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 496 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 14 ms 3224 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 408 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 456 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 496 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 16 ms 740 KB Output is correct
19 Correct 42 ms 1628 KB Output is correct
20 Correct 15 ms 1940 KB Output is correct
21 Correct 85 ms 2712 KB Output is correct
22 Correct 193 ms 3220 KB Output is correct
23 Correct 271 ms 3224 KB Output is correct