oj.uz

Submission #259636

# Submission time Handle Problem Language Result Execution time Memory
259636 2020-08-08T06:00:43 Z lyc Santa Claus (RMI19_santa) C++14
20 / 100
 1000 ms 1656 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 96068 + 5;

int T, N, X[mxN], H[mxN], V[mxN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
	cin >> T;
	while (T--) {
		cin >> N;
		FOR(i,1,N){ cin >> X[i]; }
		FOR(i,1,N){ cin >> H[i]; }
		FOR(i,1,N){ cin >> V[i]; }
		
		int totElf = 0;
		FOR(i,1,N) if (H[i] == 0) ++totElf;
		
		FOR(i,1,N){
			int ans = -1;
		
			X[0] = -1;
			FOR(k,0,N){
				if (X[k] > X[i]) break;
			
				int cnt = 0;
				multiset<int> gifts;
				multiset<int> received;
				int rt = -1;
				FOR(j,1,N){
					if (X[j] > X[i]) break;
					rt = j;
					if (H[j] == 0) {
						gifts.insert(V[j]);
						++cnt;
					} else if (X[j] <= X[k]) {
						auto it = gifts.lower_bound(V[j]);
						if (it != gifts.end()) {
							gifts.erase(it);
							received.insert(j);
						}
					}
				}
				if (cnt != totElf) break;
				
				//~ if (k < 5) continue;
				int lt = -1;
				RFOR(j,rt,1){
					if (H[j] == 1 && received.count(j) == 0) {
						auto it = gifts.lower_bound(V[j]);
						//~ if (it != gifts.end()) TRACE(j _ V[j] _ *it);
						if (it != gifts.end()) gifts.erase(it);
						if (gifts.empty()) { lt = j; break; }
					}
				}
				
				if (lt != -1) {
					int cur = 2*X[rt]-X[lt];
					//~ TRACE(k _ cur);
					if (ans == -1 || ans > cur) ans = cur;
				} //else TRACE("");
			}
			
			cout << ans << ' ';
		}
		cout << '\n';
	}
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 384 KB Output is correct
2 Correct 377 ms 504 KB Output is correct
3 Execution timed out 1059 ms 384 KB Time limit exceeded
4 Execution timed out 1082 ms 512 KB Time limit exceeded
5 Execution timed out 1073 ms 632 KB Time limit exceeded
6 Execution timed out 1085 ms 920 KB Time limit exceeded
7 Execution timed out 1086 ms 1144 KB Time limit exceeded
8 Execution timed out 1087 ms 1188 KB Time limit exceeded
9 Execution timed out 1099 ms 1528 KB Time limit exceeded
10 Execution timed out 1098 ms 1656 KB Time limit exceeded