oj.uz

Submission #57943

# Submission time Handle Problem Language Result Execution time Memory
57943 2018-07-16T14:16:28 Z E869120 Boxes with souvenirs (IOI15_boxes) C++14
10 / 100
 2 ms 380 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int v[10000009], NN, KK, LL; bool used[10000009];

int dist(int L, int R, int ty) {
	while (L >= NN) { L -= NN; R -= NN; }
	long long V1 = v[L % NN], V2 = v[R % NN];
	long long ret = min(V2, LL - V1);

	if (L < NN && R >= NN) ret = (LL - V1) + V2;
	if (ty == 1 && ((NN - L) > KK || R > KK)) return (1LL << 60);
	ret *= 2;
	return min(1LL * LL, ret);
}

int c[10000009];

long long delivery(int N, int K, int L, int pos[]) {
	NN = N; KK = K; LL = L;
	for (int i = 0; i < N; i++) v[i] = pos[i];

	for (int i = 0; i < N; i++) c[i] = dist(i, i + K - 1, 0);

	long long minx = (1LL << 60);

	for (int i = 0; i < N; i++) {
		if (used[i] == true) continue;

		long long cx = i, sum = 0;
		while (cx + K < i + N) { sum += c[cx % N]; cx += K; }

		long long ex = i;
		while (used[ex % N] == false) {
			used[ex % N] = true;
			minx = min(minx, sum + dist(cx, ex + N - 1, 0));
			//cout << ex << " " << sum + dist(cx, ex + N - 1, 0) << endl;
			sum -= c[ex % N]; ex += K; sum += c[cx%N]; cx += K;
		}
	}
	if (K * 2 < N) {
		for (int i = 0; i < N; i++) used[i] = false;
		for (int i = 0; i < N; i++) {
			if (used[i] == true) continue;

			long long cx = i, sum = 0;
			while (cx + K * 2 < i + N) { sum += c[cx % N]; cx += K; }

			long long ex = i;
			while (used[ex % N] == false) {
				used[ex % N] = true;
				minx = min(minx, sum + dist(cx, ex + N - 1, 1));
				//cout << ex << " " << sum + dist(cx, ex + N - 1, 1) << endl;
				sum -= c[ex % N]; ex += K; sum += c[cx%N]; cx += K;
			}
		}
	}
	return minx;
}

Compilation message

boxes.cpp: In function 'int dist(int, int, int)':
boxes.cpp:14:56: warning: overflow in implicit constant conversion [-Woverflow]
  if (ty == 1 && ((NN - L) > KK || R > KK)) return (1LL << 60);
                                                   ~~~~~^~~~~~
boxes.cpp:16:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return min(1LL * LL, ret);
         ~~~^~~~~~~~~~~~~~~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:38:49: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    minx = min(minx, sum + dist(cx, ex + N - 1, 0));
                                                 ^
boxes.cpp:38:43: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    minx = min(minx, sum + dist(cx, ex + N - 1, 0));
                                    ~~~~~~~^~~
boxes.cpp:54:50: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     minx = min(minx, sum + dist(cx, ex + N - 1, 1));
                                                  ^
boxes.cpp:54:44: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     minx = min(minx, sum + dist(cx, ex + N - 1, 1));
                                     ~~~~~~~^~~

Subtask #1
0 / 10.0

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

Subtask #2
10.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 Correct 2 ms 276 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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