oj.uz

Submission #73818

# Submission time Handle Problem Language Result Execution time Memory
73818 2018-08-29T05:13:27 Z nvmdava Wiring (IOI17_wiring) C++17
38 / 100
 95 ms 10220 KB 
#include "wiring.h"
#include <bits/stdc++.h>
#define INF 1000000001LL
using namespace std;

struct Node{
	long long x;
	bool col;
	Node(long long _x, bool _col){
		x = _x;
		col = _col;
	}
	bool operator<(const Node& rhs){
		return x < rhs.x;
	}
};

vector<Node> v;
int last[200005][2];
long long ans[200005], s[200005];

inline long long sum(int l, int r, int x){
	if(l == x) return s[r] - s[l - 1] - v[l].x * (r - l + 1);
	return v[r].x * (r - l + 1) - s[r] + s[l - 1];
}
inline long long func(int i, int l, int r){
	return ans[l - 1] + sum(l, r, r) + sum(r + 1, i, r + 1) + (v[r + 1].x - v[r].x) * max(r - l + 1, i - r);
}


inline void find(int i){
	int R = last[i][v[i].col ^ 1];
	int r = R ;
	int l = last[R][v[i].col] + 1;
	int m;
	ans[i] = ans[i - 1] + v[i].x - v[r].x;
	if(l == r){
		ans[i] = min(ans[i], func(i, l, R));
		return;
	}
	if(l + 1 == r){
		ans[i] = min(min(func(i, l, R), func(i, r, R)), ans[i]);
		return;
	}
	while(l + 1!= r){
		m = (l + r) >> 1;
		if(func(i, m, R) < func(i, m + 1, R)) r = m;
		else l = m;
	}
	ans[i] = min(ans[i], func(i, r, R));
}
inline void basic(int i){
	last[i][0] = last[i - 1][0];
	last[i][1] = last[i - 1][1];
	last[i][v[i].col] = i;
	s[i] = s[i - 1] + v[i].x;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	for(auto x : r){
		v.push_back(Node(x, 0));
	}
	for(auto x : b){
		v.push_back(Node(x, 1));
	}
	sort(v.begin(), v.end());
	s[0] = v[0].x;
	int i;
	
	for(i = 1; i > 0; i++){
		if(v[i].col != v[i - 1].col) break;
		basic(i);
	}
	int t = i;
	ans[t - 1] = 40000000000000000;
	for(; i < v.size(); i++){
		if(v[i].col != v[t].col) break;
		basic(i);
		ans[i] = sum(0, t - 1, t - 1) + sum(t, i, t) + (v[t].x - v[t - 1].x) * max(t, i - t + 1);
	}
	for(; i < v.size(); i++){
		basic(i);
		find(i);
	}
	return ans[v.size() - 1];
}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:75:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(; i < v.size(); i++){
        ~~^~~~~~~~~~
wiring.cpp:80:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(; i < v.size(); i++){
        ~~^~~~~~~~~~
wiring.cpp:23:34: warning: array subscript is below array bounds [-Warray-bounds]
  if(l == x) return s[r] - s[l - 1] - v[l].x * (r - l + 1);
                           ~~~~~~~^
wiring.cpp:24:46: warning: array subscript is below array bounds [-Warray-bounds]
  return v[r].x * (r - l + 1) - s[r] + s[l - 1];
                                       ~~~~~~~^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB 3rd lines differ - on the 1st token, expected: '3665', found: '4858'
5 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
3 Correct 50 ms 7004 KB Output is correct
4 Correct 52 ms 7004 KB Output is correct
5 Correct 62 ms 7388 KB Output is correct
6 Correct 52 ms 9520 KB Output is correct
7 Correct 61 ms 9520 KB Output is correct
8 Correct 63 ms 9520 KB Output is correct
9 Correct 53 ms 9520 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9520 KB Output is correct
2 Correct 2 ms 9520 KB Output is correct
3 Incorrect 74 ms 10080 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1072400611'
4 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10080 KB Output is correct
2 Correct 81 ms 10204 KB Output is correct
3 Correct 70 ms 10204 KB Output is correct
4 Correct 74 ms 10204 KB Output is correct
5 Correct 72 ms 10204 KB Output is correct
6 Correct 3 ms 10204 KB Output is correct
7 Correct 3 ms 10204 KB Output is correct
8 Correct 2 ms 10204 KB Output is correct
9 Correct 2 ms 10204 KB Output is correct
10 Correct 2 ms 10204 KB Output is correct
11 Correct 2 ms 10204 KB Output is correct
12 Correct 3 ms 10204 KB Output is correct
13 Correct 3 ms 10204 KB Output is correct
14 Correct 2 ms 10204 KB Output is correct
15 Correct 3 ms 10204 KB Output is correct
16 Correct 3 ms 10204 KB Output is correct
17 Correct 3 ms 10204 KB Output is correct
18 Correct 76 ms 10204 KB Output is correct
19 Correct 95 ms 10220 KB Output is correct
20 Correct 64 ms 10220 KB Output is correct
21 Correct 74 ms 10220 KB Output is correct
22 Correct 62 ms 10220 KB Output is correct
23 Correct 81 ms 10220 KB Output is correct
24 Correct 61 ms 10220 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB 3rd lines differ - on the 1st token, expected: '3665', found: '4858'
5 Halted 0 ms 0 KB -