oj.uz

Submission #52761

# Submission time Handle Problem Language Result Execution time Memory
52761 2018-06-26T16:56:06 Z KieranHorgan Wiring (IOI17_wiring) C++17
13 / 100
 167 ms 17276 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, ans;
vector<int> fullList;
unordered_map<int, bool> isRed, isBlue;
vector<vector<int>> segments;

int calcWire(int s, int l, int r) {
	int res = 0;
	for(int i = l; i < segments[s].size(); i++)
		res += segments[s+1][0]-segments[s][i];
	for(int i = 0; i <= r; i++)
		res += segments[s+1][i]-segments[s].back();
	res -= min((int)segments[s].size()-l, r+1)*(segments[s+1][0]-segments[s].back());
	return res;
}

long long min_total_length(vector<signed> r, vector<signed> b) {
	n = r.size();
	m = b.size();
	fullList.resize(n+m);
	merge(r.begin(), r.end(), b.begin(), b.end(), fullList.begin());
	for(auto x: r)
		isRed[x]=1;
	for(auto x: b)
		isBlue[x]=1;

	for(int i = 0; i < m+n; i++) {
		if(i==0 || isRed[fullList[i]] != isRed[fullList[i-1]]) {
			segments.push_back(vector<int>(0));
			segments.back().push_back(fullList[i]);
		} else {
			segments.back().push_back(fullList[i]);
		}
	}

	// for(auto s: segments) {
		// for(auto x: s)
			// cerr << x << " ";
		// cerr << endl;
	// }

	if(segments.size() == 2)
		return calcWire(0, 0, m-1);
	return -1;
}

Compilation message

wiring.cpp: In function 'long long int calcWire(long long int, long long int, long long int)':
wiring.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = l; i < segments[s].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 472 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 108 ms 12516 KB Output is correct
4 Correct 125 ms 12572 KB Output is correct
5 Correct 139 ms 14352 KB Output is correct
6 Correct 152 ms 17160 KB Output is correct
7 Correct 167 ms 17220 KB Output is correct
8 Correct 162 ms 17276 KB Output is correct
9 Correct 161 ms 17276 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

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