oj.uz

Submission #176103

# Submission time Handle Problem Language Result Execution time Memory
176103 2020-01-07T23:12:21 Z mat_v Boxes with souvenirs (IOI15_boxes) C++14
0 / 100
 3 ms 376 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#include "boxes.h"
#define maxn 10000005
using namespace std;
typedef long long ll;
int n,k;
int niz[maxn];
int d;
multiset<int>s;
ll dist(int l, int r){
    if(l > r)swap(l, r);
    ll res = min(r - l, l + d - r);
    return res;
}

long long delivery(int N, int K, int L, int p[]) {
    n = N, k = K, d = L;
    ff(i,1,n)niz[i] = p[i - 1];
    ff(i,1,n){
        s.insert(niz[i]);
    }
    int poz = 0;
    int cap = k;
    ll res = 0;
    while(1){
        if(s.empty())break;
        //cout << poz << " ";
        //for(auto c:s)cout << c << " ";
        //cout << "\n\n";
        if(cap == 0){
            res += dist(poz, 0);
            poz = 0;
            cap = k;
            continue;
        }
        int levi = *s.begin();
        int desni = *s.rbegin();
        int dist1 = dist(levi, poz);
        int dist2 = dist(desni, poz);
        int najbliza;
        if(dist1 < dist2)najbliza = levi;
        else najbliza = desni;
        //cout << dist(najbliza, 0) << endl;
        if(poz == 0){
            res += dist(najbliza, poz);
            poz = najbliza;
            cap--;
            s.erase(najbliza);
            continue;
        }
        if(abs(najbliza - poz) + dist(najbliza, 0) <= dist(najbliza,0) + dist(poz,0)){
            res += abs(najbliza - poz);
            poz = najbliza;
            cap--;
            s.erase(najbliza);
        }
        else{
            res += dist(poz, 0);
            poz = 0;
            cap = k;
        }
    }
    res += dist(poz, 0);
    return res;
}

Compilation message

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:39:25: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         int dist1 = dist(levi, poz);
                     ~~~~^~~~~~~~~~~
boxes.cpp:40:25: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         int dist2 = dist(desni, poz);
                     ~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -