제출 #306478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306478		Pajaraja	Teams (IOI15_teams)	C++17	34 / 100	4077 ms	158584 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
int per[25*MAXN],lc[25*MAXN],rc[25*MAXN],t,n,st[MAXN],dp[MAXN];
vector<int> l[MAXN],v,c;
void makeper(int l,int r,int ind)
{
    if(l==r) return;
    int s=(l+r)/2;
    lc[ind]=++t;
    makeper(l,s,lc[ind]);
    rc[ind]=++t;
    makeper(s+1,r,rc[ind]);
}
void makenewper(int l,int r,int v,int ind,int inh)
{
    per[ind]=per[inh]+1;
    if(l==r) return;
    int s=(l+r)/2;
    if(s>=v)
    {
        rc[ind]=rc[inh];
        lc[ind]=++t;
        makenewper(l,s,v,lc[ind],lc[inh]);
    }
    else
    {
        lc[ind]=lc[inh];
        rc[ind]=++t;
        makenewper(s+1,r,v,rc[ind],rc[inh]);
    }
}
int query(int l,int r,int lt,int rt,int ind)
{
    if(l>=lt && r<=rt) return per[ind];
    if(r<lt || l>rt) return 0;
    int s=(l+r)/2;
    return query(l,s,lt,rt,lc[ind])+query(s+1,r,lt,rt,rc[ind]);
}
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0;i<n;i++) l[B[i]].push_back(A[i]);
    makeper(1,n,t);
    int last=0;
    for(int i=n;i>0;i--)
    {
        for(int j=0;j<l[i].size();j++) {int newlast=++t; makenewper(1,n,l[i][j],newlast,last); last=newlast;}
        st[i]=last;
    }
}

int can(int M, int K[])
{
    sort(K,K+M);
    v.clear(); c.clear();
    int sz=0; for(int i=0;i<M;i++) {sz+=K[i]; if(sz>n) return 0;}
	int cnt=0;
	for(int i=0;i<M;i++)
    {
        cnt++;
        if(i==M-1 || K[i]!=K[i+1]) {v.push_back(K[i]); c.push_back(cnt); cnt=0;}
    }
    int m=v.size();
    for(int i=0;i<m;i++)
    {
        dp[i]=query(1,n,1,v[i],st[v[i]]);
        for(int j=i-1;j>=0;j--) dp[i]=min(dp[i],dp[j]+query(1,n,v[j]+1,v[i],st[v[i]]));
        dp[i]-=c[i]*v[i];
        if(dp[i]<0) return 0;
    }
    return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'void makeper(int, int, int)':
teams.cpp:7:33: warning: declaration of 'l' shadows a global declaration [-Wshadow]
    7 | void makeper(int l,int r,int ind)
      |                                 ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c;
      |             ^
teams.cpp: In function 'void makenewper(int, int, int, int, int)':
teams.cpp:16:50: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   16 | void makenewper(int l,int r,int v,int ind,int inh)
      |                                                  ^
teams.cpp:6:21: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c;
      |                     ^
teams.cpp:16:50: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   16 | void makenewper(int l,int r,int v,int ind,int inh)
      |                                                  ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c;
      |             ^
teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:34:44: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   34 | int query(int l,int r,int lt,int rt,int ind)
      |                                            ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c;
      |             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<l[i].size();j++) {int newlast=++t; makenewper(1,n,l[i][j],newlast,last); last=newlast;}
      |                     ~^~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:65:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   65 |     int m=v.size();
      |           ~~~~~~^~

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