| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 516687 | PiejanVDC | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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+1, int ri) {
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();
int cnt = 0, 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;
}
/*
#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;
}
*/