Submission #787004

#	Time	Username	Problem	Language	Result	Execution time	Memory
787004		esomer	Teams (IOI15_teams)	C++17	34 / 100	4054 ms	33104 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"

using namespace std;

typedef long long ll;

int n;
vector<vector<int>> start;

void init(int N, int* A, int* B){
	n = N;
	start.resize(n+1);
	for(int i = 0; i < n; i++){
		start[A[i]].push_back(B[i]);
	}
}

int can(int M, int* K){
	vector<int> ev(M);
	for(int i = 0; i < M; i++){
		ev[i] = K[i];
	}
	sort(ev.begin(), ev.end());
	int ind = 0;
	map<int, int> m;
	for(int i = 0; i <= n; i++){
		for(int x : start[i]){
			m[x]++;
		}
		while(ind < M && ev[ind] == i){
			int curr = 0;
			while(curr < ev[ind] && (int)m.size() > 0){
				auto it = m.begin();
				int key = (*it).first;
				int val = (*it).second;
				if(curr + val <= ev[ind]){
					m.erase(key);
					curr += val;
				}else{
					m[key] -= ev[ind] - curr;
					curr = ev[ind];
				}
			}
			if(curr != ev[ind]) return 0;
			ind++;
		}
		m.erase(i);
	}
	return 1;
}

//~ static char buffer[1024];
//~ static int currentChar = 0;
//~ static int charsNumber = 0;

//~ static inline int read() {
  //~ if (charsNumber < 0) {
    //~ exit(1);
  //~ }
  //~ if (!charsNumber || currentChar == charsNumber) {
    //~ charsNumber = (int)fread(buffer, sizeof(buffer[0]), sizeof(buffer), stdin);
    //~ currentChar = 0;
  //~ }
  //~ if (charsNumber <= 0) {
    //~ return -1;
  //~ }
  //~ return buffer[currentChar++];
//~ }

//~ static inline int readInt() {
  //~ int c, x, s;
  //~ c = read();
  //~ while (c <= 32)
    //~ c = read();
  //~ x = 0;
  //~ s = 1;
  //~ if (c == '-') {
    //~ s = -1;
    //~ c = read();
  //~ }
  //~ while (c > 32) {
    //~ x *= 10;
    //~ x += c - '0';
    //~ c = read();
  //~ }
  //~ if (s < 0)
    //~ x = -x;
  //~ return x;
//~ }

//~ int main() {
  //~ freopen("in.txt", "r", stdin);
  //~ int N;
  //~ N = readInt();
  //~ int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
  //~ int *B = (int *)malloc(sizeof(int) * (unsigned int)N);
  //~ for (int i = 0; i < N; ++i) {
    //~ A[i] = readInt();
    //~ B[i] = readInt();
  //~ }
  //~ init(N, A, B);
  //~ int Q;
  //~ Q = readInt();
  //~ for (int i = 0; i < Q; ++i) {
    //~ int M;
    //~ M = readInt();
    //~ int *K = (int *)malloc(sizeof(int) * (unsigned int)M);
    //~ for (int j = 0; j < M; ++j) {
      //~ K[j] = readInt();
    //~ }
    //~ fprintf(stdout, "%d\n", can(M, K));
  //~ }
  //~ return 0;
//}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23