oj.uz

Submission #33240

# Submission time Handle Problem Language Result Execution time Memory
33240 2017-10-23T04:29:34 Z model_code Wiring (IOI17_wiring) C++11
10 / 100
 643 ms 74084 KB 
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include "wiring.h"
using namespace std;
const int INF = 1000000005;
const int MAX = 100005;
const int TOF = 5;
vector<pair<int, int> > states;
int blue[MAX], red[MAX], n, m;
long long dp[MAX * TOF * 4];
void add_state(int i, int j)
{
	states.push_back(make_pair(i, j));
}
void create_states(int b, int r)
{
	if (blue[b] < red[r])
	{
		int lb = b + 1;
		while (lb < n && blue[lb] < red[r])
			lb++;
		int nxt_pos = INF;
		if (lb != n)
			nxt_pos = blue[lb];
		int pr = r;
		while (pr < m && red[pr] < nxt_pos)
		{
			for (int i = b; i < min(b + TOF, lb); i++)
				add_state(i, pr);
			for (int i = lb - 1; i >= max(lb - TOF, b); i--)
				add_state(i, pr);
			int mid = b + pr - r;
			for (int i = max(b, mid - TOF); i < min(mid + TOF, lb); i++)
				add_state(i, pr);
			pr++;
		}
		if (lb != n)
			create_states(lb, r);
	}
	else
	{
		int lr = r + 1;
		while (lr < m && red[lr] < blue[b])
			lr++;
		int nxt_pos = INF;
		if (lr != m)
			nxt_pos = red[lr];
		int pb = b;
		while (pb < n && blue[pb] < nxt_pos)
		{
			for (int i = r; i < min(r + TOF, lr); i++)
				add_state(pb, i);
			for (int i = lr - 1; i >= max(lr - TOF, r); i--)
				add_state(pb, i);
			int mid = r + pb - b;
			for (int i = max(r, mid - TOF); i < min(mid + TOF, lr); i++)
				add_state(pb, i);
			pb++;
		}
		if (lr != m)
			create_states(b, lr);
	}
}
int mp(pair<int, int> p)
{
	int id = lower_bound(states.begin(), states.end(), p) - states.begin();
	if (id < states.size() && states[id] == p)
		return id;
	return -1;
}
int abs(int x)
{
	return (x > 0 ? x : -x);
}
long long get(int id)
{
	if (id == -1)
		return 1e18;
	if (dp[id] != -1)
		return dp[id];
	dp[id] = 1e18;
	int i = states[id].first, j = states[id].second;
	if (!i && !j)
		return dp[id] = abs(blue[i] - red[j]);
	for (int ni = i; ni > i - 2; ni--)
		for (int nj = j; nj > j - 2; nj--)
			if (make_pair(ni, nj) != make_pair(i, j))
			{
				int nid = mp(make_pair(ni, nj));
				dp[id] = min(dp[id], get(nid) + abs(blue[i] - red[j]));
			}
	return dp[id];
}
long long min_total_length(vector <int> _red, vector <int> _blue)
{
	n = _blue.size();
	m = _red.size();
	for (int i = 0; i < n; i++)
		blue[i] = _blue[i];
	for (int i = 0; i < m; i++)
		red[i] = _red[i];
	create_states(0, 0);
	sort(states.begin(), states.end());
	states.resize(unique(states.begin(), states.end()) - states.begin());
	memset(dp, -1, sizeof(dp));
	return get(mp(make_pair(n - 1, m - 1)));
}

Compilation message

wiring.cpp: In function 'int mp(std::pair<int, int>)':
wiring.cpp:69:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (id < states.size() && states[id] == p)
         ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18428 KB Output is correct
2 Correct 0 ms 18428 KB Output is correct
3 Correct 379 ms 55076 KB Output is correct
4 Correct 636 ms 71520 KB Output is correct
5 Correct 0 ms 18428 KB Output is correct
6 Correct 0 ms 18428 KB Output is correct
7 Correct 0 ms 18428 KB Output is correct
8 Correct 6 ms 18428 KB Output is correct
9 Correct 3 ms 18428 KB Output is correct
10 Correct 0 ms 18428 KB Output is correct
11 Correct 0 ms 18428 KB Output is correct
12 Correct 0 ms 18428 KB Output is correct
13 Correct 3 ms 18428 KB Output is correct
14 Correct 0 ms 18428 KB Output is correct
15 Correct 0 ms 18428 KB Output is correct
16 Correct 0 ms 18428 KB Output is correct
17 Correct 3 ms 18572 KB Output is correct
18 Correct 409 ms 55048 KB Output is correct
19 Correct 429 ms 55040 KB Output is correct
20 Correct 643 ms 71524 KB Output is correct
21 Correct 403 ms 55028 KB Output is correct
22 Correct 449 ms 74080 KB Output is correct
23 Correct 459 ms 74080 KB Output is correct
24 Correct 456 ms 74084 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18428 KB Output is correct
2 Runtime error 349 ms 69232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

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