oj.uz

Submission #994125

# Submission time Handle Problem Language Result Execution time Memory
994125 2024-06-07T06:52:18 Z firewater Teams (IOI15_teams) C++14
100 / 100
 1112 ms 330160 KB 
#include "teams.h"
#include<bits/stdc++.h>
#define ll long long
#define MAXN 500500
#define MAXM 2024
#define fs first
#define sn second
using namespace std;
int n,B,x,y,now,w,sum,v[MAXM],c[MAXM],h[MAXN][150],g[MAXM][MAXM],f[MAXM][MAXM];
vector<pair<int,int> >d[150];
pair<int,int>a[MAXN];
void init(int N, int A[], int BB[]) {
	n=N;
	B=3500;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=n/B;++j)
			h[i][j]=0;
	for(int i=1;i<=n;++i)
		a[i]=make_pair(A[i-1],BB[i-1]);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i){
		tie(x,y)=tie(a[i].fs,a[i].sn);
		h[y][i/B]++;
		d[i/B].push_back({x,y});
	}
	for(int i=0;i<=n/B;++i)
		sort(d[i].begin(),d[i].end(),[](pair<int,int>a,pair<int,int>b){return (a.sn>b.sn);});
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n/B;++j)
			h[i][j]+=h[i][j-1];
	for(int i=n-1;i>0;--i)
		for(int j=0;j<=n/B;++j)
			h[i][j]+=h[i+1][j];
	return;
}

int can(int M, int K[]) {
	sum=0;
	w=0;
	sort(K,K+M);
	for(int i=0;i<M;++i){
		sum+=K[i];
		if(sum>n)return 0;
		if(!w||v[w]!=K[i])v[++w]=K[i],c[w]=K[i];
		else c[w]+=K[i];
	}
	for(int i=0;i<=w+1;++i)
		for(int j=0;j<=w+1;++j)
			f[i][j]=g[i][j]=0;
	for(int i=1;i<=w;++i){
		now=0;
		while((now+1)*B<=n&&a[(now+1)*B].fs<=v[i])now++;
		sum=0;
		x=0;
		for(int j=w;j>=i;--j){
			while(x<d[now].size()&&d[now][x].sn>=v[j]){
				if(d[now][x].fs<=v[i])sum++;
				x++;
			}
			g[i][j]=(now>0?h[v[j]][now-1]:0)+sum;
		}
	}
	for(int i=1;i<=w;++i)
		for(int j=i;j<=w;++j)
			f[i][j]=g[i][j]-g[i-1][j]-g[i][j+1]+g[i-1][j+1];
	for(int i=1;i<=w;++i){
		for(int j=i;j<=w;++j){
			x=min(c[i],f[i][j]);
			f[i][j]-=x;
			c[i]-=x;
		}
		if(c[i])return 0;
		for(int j=i+1;j<=w;++j)
			f[i+1][j]+=f[i][j];
	}
	return 1;
}

Compilation message

teams.cpp: In lambda function:
teams.cpp:27:48: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   27 |   sort(d[i].begin(),d[i].end(),[](pair<int,int>a,pair<int,int>b){return (a.sn>b.sn);});
      |                                   ~~~~~~~~~~~~~^
teams.cpp:11:14: note: shadowed declaration is here
   11 | pair<int,int>a[MAXN];
      |              ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:56:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    while(x<d[now].size()&&d[now][x].sn>=v[j]){
      |          ~^~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 392 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 604 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 600 KB Output is correct
26 Correct 0 ms 348 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 66784 KB Output is correct
2 Correct 62 ms 65088 KB Output is correct
3 Correct 56 ms 61520 KB Output is correct
4 Correct 59 ms 62032 KB Output is correct
5 Correct 53 ms 66636 KB Output is correct
6 Correct 52 ms 64848 KB Output is correct
7 Correct 53 ms 66640 KB Output is correct
8 Correct 55 ms 66780 KB Output is correct
9 Correct 48 ms 61780 KB Output is correct
10 Correct 45 ms 61780 KB Output is correct
11 Correct 53 ms 62548 KB Output is correct
12 Correct 47 ms 63060 KB Output is correct
13 Correct 51 ms 61780 KB Output is correct
14 Correct 54 ms 61528 KB Output is correct
15 Correct 54 ms 61728 KB Output is correct
16 Correct 57 ms 61560 KB Output is correct
17 Correct 50 ms 61780 KB Output is correct
18 Correct 52 ms 61780 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 67148 KB Output is correct
2 Correct 346 ms 67160 KB Output is correct
3 Correct 291 ms 64864 KB Output is correct
4 Correct 57 ms 62032 KB Output is correct
5 Correct 316 ms 67140 KB Output is correct
6 Correct 271 ms 67156 KB Output is correct
7 Correct 268 ms 67156 KB Output is correct
8 Correct 267 ms 67152 KB Output is correct
9 Correct 45 ms 61780 KB Output is correct
10 Correct 48 ms 62032 KB Output is correct
11 Correct 57 ms 62804 KB Output is correct
12 Correct 287 ms 63960 KB Output is correct
13 Correct 302 ms 62292 KB Output is correct
14 Correct 313 ms 63568 KB Output is correct
15 Correct 252 ms 62288 KB Output is correct
16 Correct 254 ms 62296 KB Output is correct
17 Correct 228 ms 62292 KB Output is correct
18 Correct 192 ms 62292 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 330160 KB Output is correct
2 Correct 1031 ms 330156 KB Output is correct
3 Correct 988 ms 321128 KB Output is correct
4 Correct 355 ms 313936 KB Output is correct
5 Correct 1112 ms 327504 KB Output is correct
6 Correct 1006 ms 327508 KB Output is correct
7 Correct 955 ms 327528 KB Output is correct
8 Correct 983 ms 327508 KB Output is correct
9 Correct 283 ms 311620 KB Output is correct
10 Correct 278 ms 310352 KB Output is correct
11 Correct 458 ms 316496 KB Output is correct
12 Correct 906 ms 313536 KB Output is correct
13 Correct 848 ms 313764 KB Output is correct
14 Correct 904 ms 318040 KB Output is correct
15 Correct 743 ms 314532 KB Output is correct
16 Correct 750 ms 314480 KB Output is correct
17 Correct 638 ms 313940 KB Output is correct
18 Correct 615 ms 313940 KB Output is correct