oj.uz

Submission #73542

# Submission time Handle Problem Language Result Execution time Memory
73542 2018-08-28T12:06:48 Z nvmdava Wiring (IOI17_wiring) C++17
0 / 100
 3 ms 492 KB 
#include "wiring.h"
#include <bits/stdc++.h>
#define INF 2000000007
using namespace std;

struct Con{
	int x, c;
	Con(int _x, int _c){
		x = _x;
		c = _c;
	}
	bool operator<(const Con& rhs){
		return x < rhs.x;
	}
};

vector<Con> v;
long long ans[200005], lr[200005], lb[200005], s[200005];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	v.push_back(Con(-INF, 0));
	v.push_back(Con(-INF, 1));
	
	for(auto x : r){
		v.push_back(Con(x, 0));
	}
	for(auto x : b){
		v.push_back(Con(x, 1));
	}
	sort(v.begin(), v.end());
	ans[0] = 0;
	ans[1] = 0;
	lr[0] = 0;
	lb[0] = 0;
	lr[1] = 1;
	lb[1] = 1;
	s[1] = -2 * INF;
	for(int i = 2; i < v.size(); i++){
		ans[i] = ans[i - 1];
		lr[i] = lr[i - 1];
		lb[i] = lb[i - 1];
		s[i] = s[i - 1] + v[i].x;
		if(v[i].c == 1){
			ans[i] += v[i].x - lr[i - 1];
			ans[i] = min(ans[i], ans[lr[i - 1] - 1] + s[i] - s[lr[i - 1] - 1] - v[lr[i - 1]].x * (i - lr[i - 1] + 1));
			lb[i] = i;
		} else {
			ans[i] += v[i].x - lb[i - 1];
			ans[i] = min(ans[i], ans[lb[i - 1] - 1] + s[i] - s[lb[i - 1] - 1] - v[lb[i - 1]].x * (i - lb[i - 1] + 1));
			lr[i] = i;
		}
	}
}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:12: warning: integer overflow in expression [-Woverflow]
  s[1] = -2 * INF;
            ^
wiring.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < v.size(); i++){
                 ~~^~~~~~~~~~
wiring.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB 3rd lines differ - on the 1st token, expected: '25859', found: '34641'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB 3rd lines differ - on the 1st token, expected: '904', found: '751'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 436 KB 3rd lines differ - on the 1st token, expected: '316', found: '275'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 KB 3rd lines differ - on the 1st token, expected: '27', found: '20'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB 3rd lines differ - on the 1st token, expected: '25859', found: '34641'
2 Halted 0 ms 0 KB -