Submission #226491

#	Time	Username	Problem	Language	Result	Execution time	Memory
226491		peuch	Boxes with souvenirs (IOI15_boxes)	C++17	25 / 100	5 ms	384 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e7;
const long long INF = 1e10;

#define debug(args...) // fprintf(stderr, args)

vector<int> all, maior, menor;
int dist[MAXN];
int cnt;
long long ans = 0;

bool cmp(int a, int b){
	return dist[a] < dist[b];
}

long long delivery(int N, int K, int L, int p[]) {
	cnt = N;
	int k = (int)K;
	for(int i = 0; i < N; i++){
		if(p[i] > L / 2) dist[i] = L - p[i];
		else dist[i] = p[i];
		dist[i] *= 2;
		all.push_back(i);
		if(p[i] > L / 2) maior.push_back(i);
		else menor.push_back(i);
	}
	debug("LINE 30 OK!\n");
	sort(all.begin(), all.end(), cmp);
	sort(maior.begin(), maior.end(), cmp);
	sort(menor.begin(), menor.end(), cmp);
	while(cnt > 0){
		debug("%d\n", cnt);
		long long maiorSum = (maior.size() != 0) ? dist[maior[maior.size() - 1]] : INF;
		long long menorSum = (menor.size() != 0) ? dist[menor[menor.size() - 1]] : INF;
		long long allSum = (all.size() != 0) ? L: INF;
		for(int i = all.size() - 1; i >= max((int)all.size() - k, 0); i--){
			allSum -= dist[all[i]];
		}
		debug("ALL OK\n");
		for(int i = maior.size() - 1; i >= max((int)maior.size() - k, 0); i--){
			debug("%ul\n", i);
			maiorSum -= dist[maior[i]];
		}
		debug("MAIOR OK\n");
		for(int i = menor.size() - 1; i >= max((int)menor.size() - k, 0); i--){
			menorSum -= dist[menor[i]];
		}
		debug("MENOR OK\n");
		int auxk = k;
		if(maiorSum <= allSum && maiorSum <= menorSum){
			debug("MAIOR\n");
			ans += dist[maior[maior.size() - 1]];
			for(int i = 0; i < k && !maior.empty(); i++){
				all.clear();
				maior.pop_back();
				cnt--;
				auxk--;
			}
		}
		else if(menorSum <= allSum && menorSum <= maiorSum){
			debug("MENOR\n");
			ans += dist[menor[menor.size() - 1]];
			for(int i = 0; i < k && !menor.empty(); i++){
				all.clear();
				menor.pop_back();
				cnt--;
				auxk--;
			}
		}
		else{
			debug("ALL\n");
			ans += L;
			for(int i = 0; i < k && !all.empty(); i++){
				if(p[all[all.size() - 1]] > L / 2) maior.pop_back();
				else menor.pop_back();
				all.pop_back();
				cnt--;
				auxk--;
			}
		}
		k = auxk;
		if(k == 0) k = K;
	}
	return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:39:26: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   for(int i = all.size() - 1; i >= max((int)all.size() - k, 0); i--){
               ~~~~~~~~~~~^~~
boxes.cpp:43:28: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   for(int i = maior.size() - 1; i >= max((int)maior.size() - k, 0); i--){
               ~~~~~~~~~~~~~^~~
boxes.cpp:48:28: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   for(int i = menor.size() - 1; i >= max((int)menor.size() - k, 0); i--){
               ~~~~~~~~~~~~~^~~

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