Submission #761076

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

boxes

#include "boxes.h"

#include "boxes.h"
#include <bits/stdc++.h>

//#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
 
using namespace std;
const int maxn=188500+10,LOG=17,mod=1e9+7;
int block = 200, timer = 0;
const double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define pii pair <int, int>

vector <pair <ll, ll> > fi, se;

ll solve(int K, int L)
{
	/*cout << "SOLVE\n";
	cout << "FI\n";
	for(auto i : fi) cout << i.f << " " << i.s << endl;
	cout << "SE\n";
	for(auto i : se) cout << i.f << " " << i.s << endl;*/
	int tek;
	tek = 0;
	ll S1 = 0;
	ll S2 = 0;
	ll ans = 0;
	for(auto i : fi) S1+=i.s;
	for(auto i : se) S2+=i.s;
	for(int i = (int)fi.size() - 1; i >= 0; --i)
	{
		if(tek < fi[i].s)
		{
			tek += K;
			ans += 2*fi[i].f;
		}
		tek -= fi[i].s;
	}
	tek = 0;
	for(int i = (int)se.size() - 1; i >= 0; --i)
	{
		if(tek < se[i].s)
		{
			tek += K;
			ans += 2*(L-se[i].f);
		}
		tek -= se[i].s;
	}
	ll ret = ans;
	ans = 0;
	tek = 0;
	FOR(0, i, fi.size())
	{
		if(tek < fi[i].s)
		{
			fi[i].s -= tek;
			S1 -= tek;
			tek = 0;
			if(S1 < K)
			{
				break;
			}
			tek += K;
			ans += 2*fi[i].f;
		}
		tek -= fi[i].s;
		fi[i].s = 0;
	}
	tek = 0;
	FOR(0, i, se.size())
	{
		if(tek < se[i].s)
		{
			se[i].s -= tek;
			S2 -= tek;
			tek = 0;
			if(S2 < K)
			{
				break;
			}
			tek += K;
			ans += 2*(L-se[i].f);
		}
		tek -= se[i].s;
		se[i].s = 0;
	}
	ret = min(ret, ans + L);
//	cout << "   RET " << ret << " " << ans + L << endl;
	return ret;
}

long long delivery(int N, int K, int L, int P[]) 
{
	int pos = 0;
	int cnt = 0;
	vector <pair <ll, ll> > p;
	FOR(0, i, N)
	{
		if(pos == P[i])
		{
			cnt++;
			continue;
		}
		if(pos != 0)
			p.pb({pos, cnt});
		cnt = 1;
		pos = P[i];
	}
	if(pos != 0)
		p.pb({pos, cnt});
	ll ret = 0;
	N = 0;
	FOR(0, i, p.size())
	{
		ret += p[i].s / K * 2*min(p[i].f, L-p[i].f);
		p[i].s %= K;
		N += p[i].s;
	}
	fi.clear();
	se.clear();
	if(L % 2 == 1)
	{
		int mid = L / 2;
		for(auto i : p)
		{
			if(i.f <= mid)
				fi.pb(i);
			else
				break;
		}
		for(int i = (int)p.size()-1; i >= 0; --i)
		{
			if(p[i].f <= mid) break;
			se.pb(p[i]);
		}
		return solve(K, L) + ret;
	}
	else
	{
		int mid = L / 2;
		for(auto i : p)
		{
			if(i.f < mid)
				fi.pb(i);
			else
				break;
		}
		for(int i = (int)p.size()-1; i >= 0; --i)
		{
			if(p[i].f <= mid) break;
			se.pb(p[i]);
		}
		pos = -1;
		for(int i = 0; i < (int)p.size(); ++i)
		{
			if(p[i].f == mid) pos = i;
		}
		if(pos == -1) return solve(K, L) + ret;
		ll ans = inf;
		forn(0, i, p[pos].s)
		{
			fi.pb({p[pos].f, i});
			se.pb({p[pos].f, p[pos].s-i});
			ans = min(ans, solve(K, L));
			fi.pop_back();
			se.pop_back();
		}
		return ans + ret;
	}
}

Compilation message (stderr)

boxes.cpp: In function 'long long int solve(int, int)':
boxes.cpp:10:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 | #define s second
      |           ^~~~~~
boxes.cpp:57:16: note: in expansion of macro 's'
   57 |   tek -= fi[i].s;
      |                ^
boxes.cpp:10:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 | #define s second
      |           ^~~~~~
boxes.cpp:67:16: note: in expansion of macro 's'
   67 |   tek -= se[i].s;
      |                ^
boxes.cpp:14:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   72 |  FOR(0, i, fi.size())
      |         ~~~~~~~~~~~~                   
boxes.cpp:72:2: note: in expansion of macro 'FOR'
   72 |  FOR(0, i, fi.size())
      |  ^~~
boxes.cpp:10:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 | #define s second
      |           ^~~~~~
boxes.cpp:86:16: note: in expansion of macro 's'
   86 |   tek -= fi[i].s;
      |                ^
boxes.cpp:14:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   90 |  FOR(0, i, se.size())
      |         ~~~~~~~~~~~~                   
boxes.cpp:90:2: note: in expansion of macro 'FOR'
   90 |  FOR(0, i, se.size())
      |  ^~~
boxes.cpp:10:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 | #define s second
      |           ^~~~~~
boxes.cpp:104:16: note: in expansion of macro 's'
  104 |   tek -= se[i].s;
      |                ^
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:14:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  133 |  FOR(0, i, p.size())
      |         ~~~~~~~~~~~                    
boxes.cpp:133:2: note: in expansion of macro 'FOR'
  133 |  FOR(0, i, p.size())
      |  ^~~
boxes.cpp:10:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   10 | #define s second
      |           ^~~~~~
boxes.cpp:137:13: note: in expansion of macro 's'
  137 |   N += p[i].s;
      |             ^

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