Submission #1032101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032101		SonicML	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	2396 KiB

boxes

#include <iostream>
#include <algorithm>
#include "boxes.h"
#include <vector> 

using namespace std;

typedef long long ll;

int const NMAX = 1e7;
ll preA[1 + NMAX];
ll preB[1 + NMAX];

vector <int> a;
vector <int> b;
int centre = 0;

void buildPre(int k) {
  for(int i = 0;i < a.size() && i < k;i++) {
    preA[i] = 2 * a[i];
  }
  for(int i = k;i < a.size();i++) {
    preA[i] = preA[i-k] + 2 * a[i];
  }
  for(int i = 0;i < b.size() && i < k;i++) {
    preB[i] = 2 * b[i];
  }
  for(int i = k;i < b.size();i++) {
    preB[i] = preB[i-k] + 2 * b[i];
  }
}

ll delivery(int n, int k, int l, int positions[]) {
  //cerr << "Damn, not here\n";
  for(int i = 0;i < n;i++) {
    int pos = positions[i];
    if(l % 2 == 0 && pos == l / 2) {
      centre = pos;
    } else if(pos <= l / 2) {
      a.push_back(pos);
    } else {
      b.push_back(l - pos);
    }
  }
  //cerr << "Fourth Chaos Emerald\n";
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  buildPre(k);
  //cerr << "I am all of me!\n";
  ll ans = preA[a.size()-1] + preB[b.size()-1];
  int limA = a.size()-1, limB = b.size()-1;
  //cerr << ans << '\n';
  for(int round = 1;round < (n - 1) / k + 1;round++) {
    for(int j = 0;j < k;j++) {
      if(preA[limA] - preA[limA-1] < preB[limB] - preB[limB-1]) {
        limA--;
      } else {
        limB--;
      }
    }
    ll tans = 1LL * l * round + preA[limA] + preB[limB];
    ans = min(ans, tans);
  }
  //cerr << "Just like taking candy from a baby, which is fine by me\n";
  return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'void buildPre(int)':
boxes.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int i = 0;i < a.size() && i < k;i++) {
      |                 ~~^~~~~~~~~~
boxes.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i = k;i < a.size();i++) {
      |                 ~~^~~~~~~~~~
boxes.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i = 0;i < b.size() && i < k;i++) {
      |                 ~~^~~~~~~~~~
boxes.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = k;i < b.size();i++) {
      |                 ~~^~~~~~~~~~
boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:51:22: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |   int limA = a.size()-1, limB = b.size()-1;
      |              ~~~~~~~~^~
boxes.cpp:51:41: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |   int limA = a.size()-1, limB = b.size()-1;
      |                                 ~~~~~~~~^~

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