Submission #432250

#	Time	Username	Problem	Language	Result	Execution time	Memory
432250		jeqcho	Teams (IOI15_teams)	C++17	0 / 100	4088 ms	12844 KiB

teams

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;

#define FOR(i,a,b) for(int i=a;i<b;++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for(int i=b-1;i>=a;--i)
#define R0F(i,b) ROF(i,0,b)
#define trav(a,x) for(auto&a:x)
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define pb push_back
#define sz(x) int(x.size())

int const N=5e5+3;
int A[N],B[N];
int n;
pii stu[N];
int const Q=2e5+3;
int used[Q];

// subtask 1,2

void init(int n1, int A1[], int B1[]) {
	n=n1;
	F0R(i,n)
	{
		A[i]=A1[i];
		B[i]=B1[i];
		stu[i]={A[i],B[i]};
	}
	sort(stu,stu+n);
}
int t=0;

int sum(int idex,int edex)
{
	int cnt=0;
	FOR(i,idex,edex)
	{
		if(used[i]!=t)++cnt;
	}
	return cnt;
}

void occupy(int idex,int edex)
{
	FOR(i,idex,edex)
	{
		used[i]=t;
	}
}

int can(int m, int K[]) {
	t++;
	sort(K,K+m);
	R0F(i,m)
	{
		int cnt=0;
		R0F(sta,K[i]+1)
		{
			int idex=lower_bound(stu,stu+n,pii{sta,-1})-stu;
			int edex=upper_bound(stu,stu+n,pii{sta,1e9})-stu;
			int lef=idex;
			int rig=edex-1;
			int tak=edex;
			while(lef<=rig)
			{
				int mid=(lef+rig+1)/2;
				if(cnt + sum(idex,mid+1) >= K[i])
				{
					rig=mid-1;
					tak=mid+1;
				}
				else
				{
					lef=mid+1;
				}
			}
			cnt += sum(idex,tak);
			occupy(idex,tak);
			if(cnt==K[i])break;
		}
		if(cnt!=K[i])return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:69:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   69 |    int idex=lower_bound(stu,stu+n,pii{sta,-1})-stu;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
teams.cpp:70:48: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   70 |    int edex=upper_bound(stu,stu+n,pii{sta,1e9})-stu;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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