Submission #678500

#	Time	Username	Problem	Language	Result	Execution time	Memory
678500		hello_there_123	Boxes with souvenirs (IOI15_boxes)	C++17	35 / 100	1 ms	244 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull __int128_t 
//ifstream in("input.txt");
ll delivery(int N, int K, int L, int p[]) 
{
	ll n = N;
	ll k = K;
	ll l = L;
	ll pre[k+3],pre2[k+3];
	memset(pre,0,sizeof(pre));
	memset(pre2,0,sizeof(pre2));
	deque<ull>left,right;
	for(ll i=0;i<n;i++){
		if(p[i]<=l/2) left.push_front(p[i]);
		else{
			right.push_back(l-p[i]);
		}
	}
	for(ull i=0;i<left.size();i++){
		pre[(left.size()-i-1)%k]+=left[i];
	}
	for(ull i=0;i<right.size();i++){
		pre2[(right.size()-i-1)%k]+=right[i];
	}
	ull ans = 1e18;
	for(ll i=0;i<=(n+k-1ll)/k;i++){
		ull cur = i*l;
		if(left.size() != 0) cur+=2*pre[(left.size()-1)%k];
		if(right.size() != 0) cur+=2*pre2[(right.size()-1)%k];
		//cur+=2*(pre[(left.size()-1)%k]+pre2[(right.size()-1)%k]);
		ans = min(ans,cur);
		for(ll j=0;j<k;j++){
			if(left.empty() && right.empty()) break;
			if(left.empty()){
				pre2[(right.size()-1)%k]-=right.front();
				assert(pre2[(right.size()-1)%k]>=0);
				right.pop_front();
			}
			else if(right.empty()){
				pre[(left.size()-1)%k]-=left.front();
				assert(pre[(left.size()-1)%k]>=0);
				left.pop_front();
			}
			else{
				if(left.front()>right.front()){
					pre[(left.size()-1)%k]-=left.front();
					assert(pre[(left.size()-1)%k]>=0);
					left.pop_front();
				}
				else{
					pre2[(right.size()-1)%k]-=right.front();
					assert(pre2[(right.size()-1)%k]>=0);
					right.pop_front();				
				}
				
			}
			
		}
		
	}
    assert(left.empty());
    assert(right.empty());
  	for(ll i=0;i<k;i++) if(pre[i]!=0 || pre2[i]!=0) assert(1==0);
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:22:34: warning: conversion from '__int128' to 'std::deque<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   22 |   pre[(left.size()-i-1)%k]+=left[i];
      |                                  ^
boxes.cpp:22:35: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'long long int' may change value [-Wconversion]
   22 |   pre[(left.size()-i-1)%k]+=left[i];
      |                                   ^
boxes.cpp:25:37: warning: conversion from '__int128' to 'std::deque<__int128>::size_type' {aka 'long unsigned int'} may change value [-Wconversion]
   25 |   pre2[(right.size()-i-1)%k]+=right[i];
      |                                     ^
boxes.cpp:25:38: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'long long int' may change value [-Wconversion]
   25 |   pre2[(right.size()-i-1)%k]+=right[i];
      |                                      ^
boxes.cpp:37:43: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'long long int' may change value [-Wconversion]
   37 |     pre2[(right.size()-1)%k]-=right.front();
      |                                           ^
boxes.cpp:42:40: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'long long int' may change value [-Wconversion]
   42 |     pre[(left.size()-1)%k]-=left.front();
      |                                        ^
boxes.cpp:48:41: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'long long int' may change value [-Wconversion]
   48 |      pre[(left.size()-1)%k]-=left.front();
      |                                         ^
boxes.cpp:53:44: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'long long int' may change value [-Wconversion]
   53 |      pre2[(right.size()-1)%k]-=right.front();
      |                                            ^
boxes.cpp:66:12: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
   66 |     return ans;
      |            ^~~

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