Submission #197558

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

boxes

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

long long delivery(int n, int k, int l, int positions[]) {
    long long sum = 0;
    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);
    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;
    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]) {
             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";
                }
                if(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;
                }
            }
            return sum;
        }
        else {
            bool firstHalf = false;
            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;
                    }
                }
                if(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;
                }
            }
        }
        return sum;
    }
    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;
                    }
            }
            if(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 0;
    }
    
    
    for(int i = 0; i < k; i++) {
        int counter = i;
        int delivered = i;
        bool possible = true;
        for(int j = 0; j < i-1; j++) {
            if(positions[j+1] - positions[j] > double(l/2)) {
                delivered = n;
                possible = false;
            }
        }
        if(possible) {
            sum = 0;
            if(i) {
                sum = min(2 * positions[i-1], l);
            }
            while (delivered < n)
            {
                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;
                }
            }
            
        }
    }
    return n;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:66:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             for (int i = remainde; i < n; i++) {
                          ^~~~~~~~
boxes.cpp:173:25: warning: declaration of 'delivered' shadows a previous local [-Wshadow]
                     int delivered = 0;
                         ^~~~~~~~~
boxes.cpp:157:13: note: shadowed declaration is here
         int delivered = i;
             ^~~~~~~~~
boxes.cpp:174:25: warning: declaration of 'counter' shadows a previous local [-Wshadow]
                     int counter = 0;
                         ^~~~~~~
boxes.cpp:156:13: note: shadowed declaration is here
         int counter = i;
             ^~~~~~~
boxes.cpp:156:13: warning: unused variable 'counter' [-Wunused-variable]
boxes.cpp:30:15: warning: unused variable 'bestSum' [-Wunused-variable]
     long long bestSum = n * l;
               ^~~~~~~

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