Submission #751934

#	Time	Username	Problem	Language	Result	Execution time	Memory
751934		Seb	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	212 KiB

boxes

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

using namespace std;

#define f first
#define s second

typedef long long ll;

vector <pair<ll,ll>> T;

long long delivery(int N, int K, int L, int p[]) {
    ll ans=0,cnt,l=0,r=N-1,cl=K,cr=K;
    sort(p,p+N);
    pair <ll,ll> aux = {p[0],1};
    for (int i=1;i<N;i++) {
        if (p[i]!=p[i-1]) {
            if (aux.f!=0) T.push_back(aux);
            aux = {p[i],1};
        }
        else aux.s++;
    }
    T.push_back(aux);
    for (int i=0;i<T.size();i++) {
        ans += ((T[i].s/K)*min({ll(L),2*T[i].f,2*(L-T[i].f)}));
        T[i].s %= K;
    }
    cnt = K;
    for (int i=0;i<T.size();i++) {
        if (T[i].f > L/2) break;
        if (T[i].s <= cnt) cnt -= T[i].s;
        else {
            ans += min({ll(L),2*T[i-1].f,2*(L-T[i-1].f)});
            cnt = K;
        }
        l = i;
    }
    cl = cnt;
    cnt = K;
    for (int i=T.size()-1;i>=0;i--) {
        if (T[i].f <= L/2) break;
        if (T[i].s <= cnt) cnt -= T[i].s;
        else {
            ans += min({ll(L),2*T[i+1].f,2*(L-T[i+1].f)});
            cnt = K;
        }
        r = i;
    }
    cr = cnt;
    if (2*K - (cr+cl) <= K) ans += L;
    else ans += min({ll(L),2*T[r].f,2*(L-T[r].f)}) + min({ll(L),2*T[l].f,2*(L-T[l].f)});
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:25:19: 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]
   25 |     for (int i=0;i<T.size();i++) {
      |                  ~^~~~~~~~~
boxes.cpp:30:19: 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]
   30 |     for (int i=0;i<T.size();i++) {
      |                  ~^~~~~~~~~
boxes.cpp:41:24: warning: conversion from 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   41 |     for (int i=T.size()-1;i>=0;i--) {
      |                ~~~~~~~~^~

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