oj.uz

Submission #394599

# Submission time Handle Problem Language Result Execution time Memory
394599 2021-04-27T05:24:00 Z shivensinha4 Teams (IOI15_teams) C++17
0 / 100
 96 ms 14840 KB 
#include "bits/stdc++.h"
#include "teams.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'

int n;
vi endbefore, beginafter; // both inclusive: before -> <=, after -> >=

void init(int N, int A[], int B[]) {
	n = N;
	endbefore.resize(n); beginafter.resize(n);
	for_(i, 0, n) {
		endbefore[B[i]-1]++; beginafter[A[i]-1]++;
	}
	for_(i, 1, n) endbefore[i] += endbefore[i-1];
	for (int i = n-2; i >= 0; i--) beginafter[i] += beginafter[i+1];
}

int can(int M, int K[]) {
	// return 0;
	for_(i, 0, M) K[i] -= 1;
	sort(K, K+M);
	
	int mx = 0;
	vi psum(M);
	for_(i, 0, M) psum[i] += K[i]+1;
	for_(i, 1, M) psum[i] += psum[i-1];
	
	// cout << "yoyo!" << endl;
	vi sufmx(M);
	for (int i = M-1; i >= 0; i--) {
		sufmx[i] = psum[i] + (K[i] < n-1 ? beginafter[K[i]+1] : 0);
		if (i < M-1) sufmx[i] = max(sufmx[i], sufmx[i+1]);
	}
	
	// if (K[M-1]+1 < n) {
		int ba = K[M-1]+1 < n ? beginafter[K[M-1]+1] : 0;
		int eb = K[M-1]-1 >= 0 ? endbefore[K[M-1]-1] : 0;
		// mx = K[M-1]+1 + ba + eb;
	// }
	
	for_(i, 0, M-1) {
		int val = (K[i] >= 1 ? endbefore[K[i]-1] : 0) - (i > 0 ? psum[i-1] : 0) + sufmx[i];
		mx = max(mx, val);
	}
	
	return mx <= n;
}


// int main() {
// #ifdef mlocal
// 	freopen("teams.in", "r", stdin);
// #endif
	
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
	
// 	int t; cin >> t;
// 	cout << "got " << t << endl;
// 	while (t--) {
	
// 	}
// }

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:42:7: warning: unused variable 'ba' [-Wunused-variable]
   42 |   int ba = K[M-1]+1 < n ? beginafter[K[M-1]+1] : 0;
      |       ^~
teams.cpp:43:7: warning: unused variable 'eb' [-Wunused-variable]
   43 |   int eb = K[M-1]-1 >= 0 ? endbefore[K[M-1]-1] : 0;
      |       ^~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1892 KB Output is correct
2 Correct 8 ms 2012 KB Output is correct
3 Incorrect 8 ms 2004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2380 KB Output is correct
2 Correct 16 ms 2324 KB Output is correct
3 Incorrect 31 ms 5304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9276 KB Output is correct
2 Correct 57 ms 9028 KB Output is correct
3 Incorrect 96 ms 14840 KB Output isn't correct
4 Halted 0 ms 0 KB -