제출 #434412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434412		qwerasdfzxcl	팀들 (IOI15_teams)	C++14	0 / 100	42 ms	8300 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;
int a[101][101], S[101][101], N;
pair<int, int> aa[500500];

bool cmp(pair<int, int> &x, pair<int, int> &y){
    if (x.second==y.second) return x.first<y.first;
    return x.second>y.second;
}

void init(int n, int A[], int B[]) {
    N = n;
    for (int i=0;i<n;i++) a[A[i]][B[i]]++;
    S[0][0] = a[0][0];
    for (int i=1;i<=n;i++) S[i][0] = S[i-1][0] + a[i][0];
    for (int j=1;j<=n;j++) S[0][j] = S[0][j-1] + a[0][j];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++) S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j];
    }
    for (int i=0;i<n;i++) aa[i] = {A[i], B[i]};
    sort(aa, aa+n, cmp);
    /*for (int i=0;i<=n;i++){
        for (int j=0;j<=n;j++) printf("%d ", S[i][j]);
        printf("\n");
    }*/
}

int can(int M, int K[]) {
    int s = 0;
    for (int i=0;i<M;i++) s += K[i];
    if (s>N) return 0;
    sort(K, K+M, greater<int>());
    int nxt = 0;
    multiset<int> st;
    int pt = 0;
    for (int i=0;i<M;i++){
        for (;pt<N;pt++){
            if (aa[pt].second<K[i]) break;
            st.insert(aa[pt].first);
        }
        auto iter = st.upper_bound(K[i]);
        auto iter2 = iter;
        int cnt = 0;
        while(cnt<K[i] && iter2!=st.begin()){
            --iter2; cnt++;
        }
        st.erase(iter2, iter);
        int tmp1 = S[K[i]][N];
        if (K[i]) tmp1 -= S[K[i]][K[i]-1];
        //printf("%d %d\n", K[i], tmp1);
        //if (tmp1<K[i]+nxt) return 0;
        if (cnt<K[i]){
            assert(tmp1<K[i]+nxt); return 0;
        }
        assert(cnt>=K[i]);
        if (i<M-1){
            int tmp2 = S[K[i+1]][N];
            if (K[i]) tmp2 -= S[K[i+1]][K[i]-1];
            int tmp3 = tmp1-tmp2;
            if (tmp3<K[i]+nxt) nxt = K[i]+nxt-tmp3;
            else nxt = 0;
        }
    }
    return 1;
}

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