Submission #922742

#	Time	Username	Problem	Language	Result	Execution time	Memory
922742		Aiperiii	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	1 ms	440 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
int dist(int x,int y,int L){
   if(x>y)swap(x,y);
   return min(y-x,L-y+x);
}
long long delivery(int N, int K, int L, int p[]) {
   map <int,int> mp;
   for(int i=0;i<N;i++){
      mp[p[i]]++;
   }
   set <int> st;
   for(auto x : mp){
      st.insert(x.ff);
   }
   int cur=0,pres=K;
   long long ans=0;
   while(!st.empty()){
      auto it=st.upper_bound(cur);
      int next=-1,mn=1e9;
      if(it!=st.end()){
         if(dist(cur,*it,L)<mn){
            mn=dist(cur,*it,L);
            next=*it;
         }
      }
      if(it!=st.begin()){
         it--;
         if(dist(cur,*it,L)<mn){
            mn=dist(cur,*it,L);
            next=*it;
         }
      }
      ans+=(long long)mn;
      cur=next;
      int x=mp[cur];
      mp[cur]-=min(x,pres);
      pres-=min(x,pres);
      if(mp[cur]==0)st.erase(cur);
      if(pres==0){
         pres=K;
         ans+=(long long)dist(cur,0,L);
         cur=0;
      }
   }
   ans+=(long long)dist(cur,0,L);
   return ans;
}
/*
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int n,k,l;
   cin>>n>>k>>l;
   int pos[n];
   for(int i=0;i<n;i++)cin>>pos[i];
   cout<<delivery(n,k,l,pos);
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30