oj.uz

Submission #1036411

# Submission time Handle Problem Language Result Execution time Memory
1036411 2024-07-27T10:40:33 Z beaconmc Wiring (IOI17_wiring) C++14
17 / 100
 538 ms 115384 KB 
#include "wiring.h"
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
 
 
ll n,m;
vector<ll> R,B;
unordered_map<int,ll> cache;
unordered_map<int,ll> poses;
bool flag;
ll dp(ll x, ll y){
	if (flag && abs(poses[R[x]]-poses[B[y]]) > 20) return 1000000000000000;
	if (cache.count(x*1000000+y)) return cache[x*1000000+y];
	if (x==n && y==m) return 0;
	if (x>=n || y >= m) return 1000000000000000;
    
 
	return cache[x*1000000+y] = min(dp(x+1,y), min(dp(x,y+1), dp(x+1,y+1))) + abs(R[x] - B[y]);
}
 
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	R.clear();
	B.clear();
	vector<ll> stuff;
	for (auto&i : r) stuff.push_back(i);
	for (auto&i : b) stuff.push_back(i);
	flag = false;
	if (r.size() > 200 || b.size() > 200) flag = true;
 
	sort(stuff.begin(), stuff.end());
	FOR(i,0,stuff.size()){
		poses[stuff[i]] = i;
	}
 
	cache.clear();
	for (auto&i : r) R.push_back(i);
	for (auto&i : b) B.push_back(i);
	n = r.size();
	m = b.size();
	return dp(0,0);
}

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:5:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   36 |  FOR(i,0,stuff.size()){
      |      ~~~~~~~~~~~~~~~~            
wiring.cpp:36:2: note: in expansion of macro 'FOR'
   36 |  FOR(i,0,stuff.size()){
      |  ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 4 ms 1976 KB Output is correct
8 Correct 4 ms 2060 KB Output is correct
9 Correct 3 ms 1976 KB Output is correct
10 Correct 3 ms 2060 KB Output is correct
11 Correct 4 ms 1976 KB Output is correct
12 Correct 3 ms 1976 KB Output is correct
13 Correct 3 ms 1976 KB Output is correct
14 Correct 4 ms 1976 KB Output is correct
15 Correct 3 ms 1976 KB Output is correct
16 Correct 4 ms 1976 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Incorrect 36 ms 11968 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '1000000000000000'
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 528 ms 109524 KB Output is correct
4 Correct 476 ms 115380 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 424 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 506 ms 109352 KB Output is correct
19 Correct 500 ms 109240 KB Output is correct
20 Correct 524 ms 115384 KB Output is correct
21 Correct 538 ms 109240 KB Output is correct
22 Correct 525 ms 109748 KB Output is correct
23 Correct 494 ms 109748 KB Output is correct
24 Correct 492 ms 109752 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 4 ms 1976 KB Output is correct
8 Correct 4 ms 2060 KB Output is correct
9 Correct 3 ms 1976 KB Output is correct
10 Correct 3 ms 2060 KB Output is correct
11 Correct 4 ms 1976 KB Output is correct
12 Correct 3 ms 1976 KB Output is correct
13 Correct 3 ms 1976 KB Output is correct
14 Correct 4 ms 1976 KB Output is correct
15 Correct 3 ms 1976 KB Output is correct
16 Correct 4 ms 1976 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 2 ms 1116 KB Output is correct
19 Incorrect 36 ms 11968 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '1000000000000000'
20 Halted 0 ms 0 KB -