Submission #1041673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041673		vjudge1	Segway (COI19_segway)	C++17	100 / 100	271 ms	3224 KiB

segway

//~~~~~~~~~~~~~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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45