oj.uz

Submission #853019

# Submission time Handle Problem Language Result Execution time Memory
853019 2023-09-23T10:30:39 Z waldi Roller Coaster Railroad (IOI16_railroad) C++17
34 / 100
 498 ms 83556 KB 
#include <bits/stdc++.h>
#include "railroad.h"
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define inf 1000000000000000000ll
#define infmale 1000000000ll
using namespace std;
typedef long long ll;

struct przedzialowiec{
	int n;
	vector<vector<ll>> liscie;
	vector<ll> mini;
	przedzialowiec(int nn){
		for(n = 1; n < nn;) n <<= 1;
		liscie.resize(n<<1);
		mini.resize(n<<1, inf);
	}
	void wrzuc(int poz, ll wart){
		liscie[poz+n-1].emplace_back(wart);
	}
	void zbuduj(){
		FOR(i, n, n+n-1){
			sort(liscie[i].begin(), liscie[i].end(), greater<ll>());
			if(liscie[i].size()) mini[i] = liscie[i].back();
		}
		for(int i = n; --i;) mini[i] = min(mini[i<<1], mini[i<<1|1]);
	}
	ll mini_prz(int p, int k, int tp, int tk, int w){
		if(p <= tp && tk <= k) return mini[w];
		int sr = (tp+tk)>>1;
		ll ret = inf;
		if(p <= sr) ret = min(ret, mini_prz(p, k, tp, sr, w<<1));
		if(sr < k) ret = min(ret, mini_prz(p, k, sr+1, tk, w<<1|1));
		return ret;
	}
	ll mini_prz(int p, int k){
		return mini_prz(p, k, 1, n, 1);
	}
	void usun(int poz){
		poz += n-1;
		liscie[poz].pop_back();
		mini[poz] = liscie[poz].size() ? liscie[poz].back() : inf;
		while(poz >>= 1) mini[poz] = min(mini[poz<<1], mini[poz<<1|1]);
	}
};

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = s.size();
	
	if(n <= 16){
		vector<vector<ll>> dp(1<<n, vector<ll>(n, inf));
		FOR(maska, 1, (1<<n)-1) REP(ost, n) if(maska>>ost&1){
			if(__builtin_popcount(maska) == 1) dp[maska][ost] = 0ll;
			REP(i, n) if(!(maska>>i&1)) dp[maska+(1<<i)][i] = min(dp[maska+(1<<i)][i], dp[maska][ost] + max(0, t[ost]-s[i]));
		}
		ll wyn = inf;
		REP(i, n) wyn = min(wyn, dp[(1<<n)-1][i]);
		return wyn;
	}
	
	set<int> secik;
	for(int x : s) secik.emplace(x);
	for(int x : t) secik.emplace(x);
	unordered_map<int, int> mapa;
	int it = 0;
	for(int x : secik) mapa[x] = ++it;
	for(int &x : s) x = mapa[x];
	for(int &x : t) x = mapa[x];
	
	int ost = 1;
	przedzialowiec prz(it);
	REP(i, n) prz.wrzuc(s[i], t[i]*infmale+s[i]);
	prz.zbuduj();
	REP(xd, n){
		ll mini = prz.mini_prz(ost, it);
		if(mini == inf) return 1ll;
		ost = mini/infmale;
		prz.usun(mini%infmale);
		// i = gosc o minimalnym t[i] sposrod gosci o s[i]>=ost
		// nie istnieje? return 1ll;
		// ost = t[i]
		// wywal goscia i
	}
	return 0ll;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 344 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 344 KB n = 2
6 Correct 0 ms 344 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 1 ms 344 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 1 ms 344 KB n = 8
11 Correct 0 ms 600 KB n = 8
12 Correct 0 ms 344 KB n = 8
13 Correct 1 ms 344 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 0 ms 348 KB n = 8
16 Correct 1 ms 344 KB n = 8
17 Correct 0 ms 344 KB n = 8
18 Correct 0 ms 344 KB n = 8
19 Correct 0 ms 600 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 0 ms 344 KB n = 8
22 Correct 0 ms 344 KB n = 8
23 Correct 0 ms 344 KB n = 8
24 Correct 0 ms 344 KB n = 8
25 Correct 1 ms 344 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 344 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 344 KB n = 2
6 Correct 0 ms 344 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 1 ms 344 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 1 ms 344 KB n = 8
11 Correct 0 ms 600 KB n = 8
12 Correct 0 ms 344 KB n = 8
13 Correct 1 ms 344 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 0 ms 348 KB n = 8
16 Correct 1 ms 344 KB n = 8
17 Correct 0 ms 344 KB n = 8
18 Correct 0 ms 344 KB n = 8
19 Correct 0 ms 600 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 0 ms 344 KB n = 8
22 Correct 0 ms 344 KB n = 8
23 Correct 0 ms 344 KB n = 8
24 Correct 0 ms 344 KB n = 8
25 Correct 1 ms 344 KB n = 8
26 Correct 1 ms 344 KB n = 8
27 Correct 0 ms 344 KB n = 8
28 Correct 0 ms 344 KB n = 8
29 Correct 35 ms 11096 KB n = 16
30 Correct 35 ms 11096 KB n = 16
31 Correct 38 ms 11096 KB n = 16
32 Correct 36 ms 11096 KB n = 16
33 Correct 44 ms 11192 KB n = 16
34 Correct 36 ms 11096 KB n = 16
35 Correct 36 ms 11100 KB n = 16
36 Correct 16 ms 5208 KB n = 15
37 Correct 1 ms 344 KB n = 8
38 Correct 34 ms 11096 KB n = 16
39 Correct 36 ms 11100 KB n = 16
40 Correct 1 ms 344 KB n = 9
41 Correct 44 ms 11344 KB n = 16
42 Correct 44 ms 11096 KB n = 16
43 Correct 34 ms 11096 KB n = 16
44 Correct 0 ms 344 KB n = 9
45 Correct 17 ms 5208 KB n = 15
46 Correct 41 ms 11096 KB n = 16
47 Correct 35 ms 11096 KB n = 16
48 Correct 35 ms 11096 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 79292 KB n = 199999
2 Correct 482 ms 83412 KB n = 199991
3 Correct 462 ms 83556 KB n = 199993
4 Incorrect 364 ms 69732 KB answer is not correct: 1 instead of 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 344 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 344 KB n = 2
6 Correct 0 ms 344 KB n = 2
7 Correct 0 ms 348 KB n = 3
8 Correct 1 ms 344 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 1 ms 344 KB n = 8
11 Correct 0 ms 600 KB n = 8
12 Correct 0 ms 344 KB n = 8
13 Correct 1 ms 344 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 0 ms 348 KB n = 8
16 Correct 1 ms 344 KB n = 8
17 Correct 0 ms 344 KB n = 8
18 Correct 0 ms 344 KB n = 8
19 Correct 0 ms 600 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 0 ms 344 KB n = 8
22 Correct 0 ms 344 KB n = 8
23 Correct 0 ms 344 KB n = 8
24 Correct 0 ms 344 KB n = 8
25 Correct 1 ms 344 KB n = 8
26 Correct 1 ms 344 KB n = 8
27 Correct 0 ms 344 KB n = 8
28 Correct 0 ms 344 KB n = 8
29 Correct 35 ms 11096 KB n = 16
30 Correct 35 ms 11096 KB n = 16
31 Correct 38 ms 11096 KB n = 16
32 Correct 36 ms 11096 KB n = 16
33 Correct 44 ms 11192 KB n = 16
34 Correct 36 ms 11096 KB n = 16
35 Correct 36 ms 11100 KB n = 16
36 Correct 16 ms 5208 KB n = 15
37 Correct 1 ms 344 KB n = 8
38 Correct 34 ms 11096 KB n = 16
39 Correct 36 ms 11100 KB n = 16
40 Correct 1 ms 344 KB n = 9
41 Correct 44 ms 11344 KB n = 16
42 Correct 44 ms 11096 KB n = 16
43 Correct 34 ms 11096 KB n = 16
44 Correct 0 ms 344 KB n = 9
45 Correct 17 ms 5208 KB n = 15
46 Correct 41 ms 11096 KB n = 16
47 Correct 35 ms 11096 KB n = 16
48 Correct 35 ms 11096 KB n = 16
49 Correct 498 ms 79292 KB n = 199999
50 Correct 482 ms 83412 KB n = 199991
51 Correct 462 ms 83556 KB n = 199993
52 Incorrect 364 ms 69732 KB answer is not correct: 1 instead of 0
53 Halted 0 ms 0 KB -