Submission #516688

#	Time	Username	Problem	Language	Result	Execution time	Memory
516688		PiejanVDC	Teams (IOI15_teams)	C++17	0 / 100	4096 ms	12840 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"
using namespace std;

vector<int>sum;
vector<int>rem;

vector<int>a,b;

void init(int N, int A[], int B[]) {
    sum.resize(N+5,0);
    rem.resize(N+5,0);
    for(int i = 0 ; i < N ; i++)
        sum[A[i]]++,sum[B[i]+1]--,a.push_back(A[i]),b.push_back(B[i]);
    for(int i = 1 ; i <= N ; i++)
        sum[i] += sum[i-1];
}

int r(int le, int ri) {
    le++;
    int ret = 0;
    for(int i = 0 ; i < (int)a.size() ; i++) {
        if(a[i] <= le && b[i] < ri)
            ret++;
    }
    return ret;
}

int can(int m, int k[]) {
    bool ok = 1;
    vector<pair<int,int>>v;
    sort(k,k+m);
    int cnt = 0, val = -1;
    for(int i = 0 ; i < m ; i++) {
        if(k[i] != val) {
            v.push_back({val,cnt});
            cnt = 1;
            val = k[i];
        }
        cnt++;
    }
    v.push_back({val,cnt});
    m = (int)v.size();
    cnt = 0; int prev = 0;
    for(int i = 0 ; i < m ; i++) {
        int z = v[i].first;
        int am = sum[z] - sum[prev];
        int removed = r(prev,z);
        cnt = max(0,(cnt - (removed)));
        am -= cnt;
        if(am < z*v[i].second) {
            ok = 0;
            break;
        }
        cnt += z*v[i].second;
        prev = z-1;
    }
    return ok;
}

//signed main() {}

/*
#include <stdio.h>
#include <stdlib.h>

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;

int main() {
	//_inputFile = fopen("teams.in", "rb");
	//_outputFile = fopen("teams.out", "w");
    int N;
    cin>>N;
    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) {
    	cin>>A[i]>>B[i];
    }
    init(N, A, B);
    int Q;
    cin>>Q;
    for (int i = 0; i < Q; ++i) {
    	int M;
        cin>>M;
        int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		cin>>K[j];
    	}
    	printf("%d\n", can(M, K));
    }
    return 0;
}
*/

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