Submission #197571

#	Time	Username	Problem	Language	Result	Execution time	Memory
197571		AaronNaidu	Boxes with souvenirs (IOI15_boxes)	C++14	35 / 100	2 ms	380 KiB

boxes

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

long long delivery(int n, int k, int l, int positions[]) {
    long long sum = 0;
    long long minSum;
    if(k == 1) {
        //cout << "In branch\n";
        for(int i = 0; i < n; i++) {
            //cout << "Value " << positions[i] << "\n";
            sum += 2 * min(positions[i], l - positions[i]);
            //cout << "Sum now " << sum << "\n"; 
        }
        return sum;
    }
    sort(positions, positions + n);
    long long zeroes;
    for (int i = 0; i < n; i++)
    {
        if(positions[i] == 0) {
            zeroes++;
        }
        else {
            break;
        }
    }
    n -= zeroes;
    for (int i = 0; i < n; i++)
    {
        positions[i] = positions[i+zeroes];
    }
    if(k >= n) {
        if(positions[0] > (double) l/2) {
            return 2 * (l - positions[0]);
        }
        if(positions[n-1] < (double) l/2) {
            return 2 * positions[n-1];
        }
        for(int i = 0; i < n-1; i++) {
            if(positions[i+1] - positions[i] > double(l/2)) {
                return 2 * (positions[i] + (l - positions[i+1]));
            }
        }
        return l;
    }
    long long bestSum = n * l;
    if(positions[0] > (double) l/2) {
        int delivered = 0;
        int counter = 0;
        while(delivered < n) {
            delivered += k;
            sum += 2 * (l - positions[counter]);
            counter += k;
        }
        return sum;
    }
    if(positions[n-1] < (double) l/2) {
        int delivered = 0;
        int counter = 0;
        reverse(positions, positions + n);
        while(delivered < n) {
            delivered += k;
            sum += 2 * positions[counter];
            counter += k;
        }
        return sum;
    }
    
    
    
    long long remainde = n%k;
    long long trial = 0;
    long long trial2 = 0;
    long long point = -1;
    sum = 0;
    long long trialNew = 0;
    if (remainde)
    {
        //cout << "Was remainder\n";
        //cout << "It's " << positions[remainde - 1] << "vs" << n- positions[n-remainde] << "\n";
        //if (positions[remainde - 1] < l - positions[n-remainde]) {
        if(true) {
             bool firstHalf = false;
            //cout << "Cut out first \n";
            sum += min(2 * positions[remainde - 1], l);
            //cout << "Initial sum " << sum << "\n";
            for (int i = remainde; i < n; i++) {
                point++;
                if(point % k == 0) {
                    trial =  2 * min(positions[i], l - positions[i]);
                    if(positions[i] < double (l/2)) {
                        firstHalf = true;
                    }
                    else {
                        firstHalf = false;
                    }
                    //cout << "Start with distance " << trial << "\n";
                }
                trial2 = 2 * min(positions[i], l - positions[i]);
                trial = max(trial, trial2);
                if(point % k == k-1 or i == n-1 or positions[i+1] - positions[i] > double(l/2)) {
                    trial2 = 2 * min(positions[i], l - positions[i]);
                    //cout << "End with distance " << trial << "\n";
                    trial = max(trial, trial2);
                    if(firstHalf and positions[i] > double (l/2)) {
                        sum += l;
                    }
                    else {
                        sum += trial;
                    }
                    
                    point = -1;
                }
            }
        
        }
        if(true) {
            bool firstHalf = false;
            minSum = sum;
            sum = 0;
            sum += min(l, 2 * (n - positions[n-remainde]));
            for (int i = 0; i < n-remainde; i++) {
                point++;
                if(point % k == 0) {
                    trial =  2 * min(positions[i], l - positions[i]);
                    if(positions[i] < double (l/2)) {
                        firstHalf = true;
                    }
                    else {
                        firstHalf = false;
                    }
                }
                trial2 = 2 * min(positions[i], l - positions[i]);
                trial = max(trial, trial2);
                if(point % k == k-1 or i == n-1-remainde or positions[i+1] - positions[i] > double(l/2)) {
                    trial2 = 2 * min(positions[i], l - positions[i]);
                    trial = max(trial, trial2);
                    if(firstHalf and positions[i] > double (l/2)) {
                        sum += l;
                    }
                    else {
                        sum += trial;
                    }
                    
                    point = -1;
                }
            }
        }
        minSum = min(minSum, sum);
        return minSum;
    }
    else {
         bool firstHalf = false;
        for (int i = 0; i < n; i++)
        {
            point++;
            if(point % k == 0) {
                trial =  2 * min(positions[i], l - positions[i]);
                if(positions[i] < double (l/2)) {
                        firstHalf = true;
                    }
                    else {
                        firstHalf = false;
                    }
            }
            trial2 = 2 * min(positions[i], l - positions[i]);
            trial = max(trial, trial2);
            if(point % k == k-1 or i == n-1 or positions[i+1] - positions[i] > double(l/2)) {
                trial2 = 2 * min(positions[i], l - positions[i]);
                    trial = max(trial, trial2);
                    if(firstHalf and positions[i] > double (l/2)) {
                        sum += l;
                    }
                    else {
                        sum += trial;
                    }
                    
                    point = -1;
            }
        }
        return sum;
    }
    
    for(;;) {

    }
    return n;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:27:7: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     n -= zeroes;
     ~~^~~~~~~~~
boxes.cpp:87:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             for (int i = remainde; i < n; i++) {
                          ^~~~~~~~
boxes.cpp:46:15: warning: unused variable 'bestSum' [-Wunused-variable]
     long long bestSum = n * l;
               ^~~~~~~
boxes.cpp:76:15: warning: unused variable 'trialNew' [-Wunused-variable]
     long long trialNew = 0;
               ^~~~~~~~
boxes.cpp:17:15: warning: 'zeroes' may be used uninitialized in this function [-Wmaybe-uninitialized]
     long long zeroes;
               ^~~~~~

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