oj.uz

Submission #826458

# Submission time Handle Problem Language Result Execution time Memory
826458 2023-08-15T15:26:47 Z caganyanmaz Wiring (IOI17_wiring) C++17
13 / 100
 23 ms 4976 KB 
#include <bits/stdc++.h>
//#define DEBUGGING
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif


constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG =  9;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e10;
deque<int> r, b;



long long subtask2()
{
	int m = r.back();
	int sum = 0;
	for (int i : r)
		sum += m - i;
	for (int i : b)
		sum += i - m;
	if (r.size() > b.size())
		sum += (b[0] - m) * (r.size() - b.size());
	return sum;
}

vector<int> dp(MXG);
vector<int> dp2(MXG);

long long min_total_length(vector<int32_t> rr, vector<int32_t> bb) 
{
	for (int i : rr)
		r.push_back(i);
	for (int i : bb)
		b.push_back(i);
	if (r.back() < b[0])
		return subtask2();
	int g = 200;
	if (rr.size() > 200 || bb.size() > 200)
		g = 9;
	int current = 0;
	fill(dp.begin(), dp.begin() + g, INF);
	dp[0] = 0;
	if (r[0] > b[0])
		swap(r, b);
	int mnr = -INF;
	debug(dp);
	while (r.size() || b.size())
	{
		debug(r, b);
		vector<int> v;
		assert(v.size() < g);
		while (r.size() && (b.empty() || r[0] < b[0])) 
		{
			v.pb(r[0]);
			r.pop_front();
		}
		fill(dp2.begin(), dp2.begin() + g, INF);
		int rb = b[0], lb = v[0];
		for (int i = 0; i <= v.size(); i++) // How many we're putting to right
		{
			int lsum = 0;
			int rsum = 0;
			for (int j = 0; j < v.size()-i; j++)
				lsum += v[j] - lb;
			for (int j = v.size()-i; j < v.size(); j++)
				rsum += rb - v[i];
			debug(lsum, rsum);
			for (int j = 0; j < g; j++) // How many is coming from right
			{
				if (j < v.size()-i) // We need to take more
					dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
				else
					dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);
				// We might need to give more as well (but it has 0 contribution so it doesn't matter)
			}

		}
		for (int i = 0; i < g; i++)
			dp[i] = dp2[i];
		debug(dp);
		mnr = v.back();
		swap(r, b);
	}
	return dp[0];
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from wiring.cpp:1:
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   64 |   assert(v.size() < g);
      |          ~~~~~~~~~^~~
wiring.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int i = 0; i <= v.size(); i++) // How many we're putting to right
      |                   ~~^~~~~~~~~~~
wiring.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   76 |    for (int j = 0; j < v.size()-i; j++)
      |                    ~~^~~~~~~~~~~~
wiring.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for (int j = v.size()-i; j < v.size(); j++)
      |                             ~~^~~~~~~~~~
wiring.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   83 |     if (j < v.size()-i) // We need to take more
      |         ~~^~~~~~~~~~~~
wiring.cpp:53:6: warning: unused variable 'current' [-Wunused-variable]
   53 |  int current = 0;
      |      ^~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 14 ms 3748 KB Output is correct
4 Correct 13 ms 3900 KB Output is correct
5 Correct 14 ms 3980 KB Output is correct
6 Correct 19 ms 4748 KB Output is correct
7 Correct 23 ms 4976 KB Output is correct
8 Correct 21 ms 4624 KB Output is correct
9 Correct 18 ms 4792 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

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