oj.uz

답안 #135733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135733 2019-07-24T10:21:39 Z evpipis 팀들 (IOI15_teams) C++11
100 / 100
 1544 ms 349788 KB 
//#define TEST

#ifndef TEST
#include "teams.h"
#endif // TEST

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 5e5+5;
vector<int> stud[len];
int team[len], n, dp[len], pre[len], nex[len], in[len];
priority_queue<ii, vector<ii>, greater<ii> > pq;

struct node{
    int sum;
    node *left, *right;

    node(int s = 0, node *l = NULL, node *r = NULL){
        sum = s;
        left = l;
        right = r;
    }
};

typedef node* pnode;
pnode null = new node(), root[len];

pnode update(pnode t, int l, int r, int i){
    if (l == r)
        return new node(t->sum+1, null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(t->sum+1, update(t->left, l, mid, i), t->right);
    return new node(t->sum+1, t->left, update(t->right, mid+1, r, i));
}

int ask(pnode a, pnode b, int l, int r, int i, int j){
    if (r < i || j < l || i > j)
        return 0;
    if (i <= l && r <= j)
        return (a->sum-b->sum);

    int mid = (l+r)/2;
    return ask(a->left, b->left, l, mid, i, j) + ask(a->right, b->right, mid+1, r, i, j);
}

int query(pnode a, pnode b, int l, int r, int x){
    //printf("l = %d, r = %d, x = %d\n", l, r, x);
    if (l == r){
        if ((a->sum-b->sum) <= x)
            return l;
        return l+1;
    }

    int mid = (l+r)/2, rig = (a->right->sum-b->right->sum);
    if (rig <= x)
        return query(a->left, b->left, l, mid, x-rig);
    return query(a->right, b->right, mid+1, r, x);
}

void init(int N, int A[], int B[]){
    n = N;
    for (int i = 1; i <= n; i++)
        stud[i].clear();
    for (int i = 0; i < n; i++)
        stud[A[i]].pb(B[i]);

    //for (int i = 0; i < n; i++)
      //  printf("student: %d - %d\n", A[i], B[i]);


    root[0] = null->left = null->right = null;
    for (int i = 1; i <= n; i++){
        root[i] = root[i-1];
        for (int j = 0; j < stud[i].size(); j++)
            root[i] = update(root[i], 1, n, stud[i][j]);
    }
}

int can(int m, int K[]){
    for (int i = 1; i <= m; i++)
        team[i] = K[i-1];
    sort(team+1, team+m+1);

    int sum = 0;
    for (int i = 1; i <= m; i++)
        sum = min(n+1, team[i]+sum);

    if (sum > n)
        return 0;

    /*printf("team =\n");
    for (int i = 1; i <= m; i++)
        printf("%d ", team[i]);
    printf("\n");*/

    while (!pq.empty())
        pq.pop();
    for (int i = 0; i <= m; i++){
        in[i] = 0;
        pre[i] = -1;
        nex[i] = -1;
    }
    in[0] = 1, pre[0] = -1, nex[0] = -1;

    int ans = 1, opt = 0;
    for (int i = 1; i <= m; i++){
        while (!pq.empty() && pq.top().fi <= team[i]){
            ii cur = pq.top();
            pq.pop();

            if (!in[cur.se]) continue;
            in[cur.se] = 0;

            int pr = pre[cur.se], ne = nex[cur.se];
            nex[pr] = ne;
            if (ne == -1){
                opt = pr;
            }
            else{
                pre[ne] = pr;
                //printf("%d with %d: %d\n", pr, ne, query(root[team[ne]], root[team[pr]], 1, n, dp[ne]-dp[pr]));
                pq.push(mp(query(root[team[ne]], root[team[pr]], 1, n, dp[ne]-dp[pr]), ne));
            }
        }

        int tim = query(root[team[i-1]], root[team[opt]], 1, n, dp[i-1]-dp[opt]);
        //printf("%d with %d: %d\n", opt, i-1, tim);
        if (i != 1 && tim > team[i]){
            in[i-1] = 1;
            nex[opt] = i-1;
            pre[i-1] = opt;
            nex[i-1] = -1;
            opt = i-1;
            pq.push(mp(tim, opt));
        }

        //printf("i = %d, team = %d, opt = %d\n", i, team[i], opt);

        dp[i] = dp[opt]+ask(root[team[i]], root[team[opt]], 1, n, team[i], n)-team[i];

        //printf("i = %d, dp = %d\n", i, dp[i]);

        //printf("i = %d, opt = %d, dp = %d\n", i, opt, dp[i]);
        /*printf("all opts:");
        for (int j = opt; j != -1; j = pre[j])
            printf(" %d", j);
        printf("\n");*/
        if (dp[i] < 0)
            ans = 0;
    }
    //printf("ans = %d\n", ans);
	return ans;
}

#ifdef TEST

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

int main() {
    for (int t = 1; t <= 30; t++){
        char test[10];
        if (t < 10)
            sprintf(test, "0%d", t);
        else
            sprintf(test, "%d", t);

        printf("test file %s\n", test);

        _inputFile = fopen(test, "rb");

        //_outputFile = fopen("teams2.out", "w");
        int N;
        N = _readInt();
        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) {
            A[i] = _readInt();
            B[i] = _readInt();
        }

        if (N <= 1000)
            init(N, A, B);

        printf("N = %d\n", N);

        //vector<int> hel;
        //hel.clear();

        int Q;
        Q = _readInt();
        //Q = 1;
        printf("Q = %d\n", Q);
        for (int i = 0; i < Q; ++i) {
            //printf("quere number %d\n", i);
            int M;
            M = _readInt();
            //printf("M = %d\n", M);
        int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
            for (int j = 0; j < M; ++j) {
                K[j] = _readInt();
            }

            /*printf("M = %d\n", M);
            for (int j = 0; j < M; j++)
                printf("%d ", K[j]);
            printf("\n");*/

            if (N <= 1000){
                //hel.pb(can(M, K));
                fprintf(_outputFile,"%d\n", can(M, K));
            }
        }

        /*if (0){
            if (t < 10)
                sprintf(test, "0%d.a", t);
            else
                sprintf(test, "%d.a", t);
            _inputFile = fopen(test, "rb");

            for (int i = 0; i < Q; i++){
                int cor = _readInt();
                if (cor != hel[i])
                    printf("my answer = %d, correct = %d\n", hel[i], cor);
            }
        }*/
    }
    return 0;
}
#endif // TEST

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:83:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < stud[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12156 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 14 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12204 KB Output is correct
6 Correct 13 ms 12332 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 13 ms 12152 KB Output is correct
9 Correct 13 ms 12152 KB Output is correct
10 Correct 13 ms 12156 KB Output is correct
11 Correct 13 ms 12156 KB Output is correct
12 Correct 13 ms 12152 KB Output is correct
13 Correct 13 ms 12152 KB Output is correct
14 Correct 13 ms 12152 KB Output is correct
15 Correct 13 ms 12280 KB Output is correct
16 Correct 13 ms 12124 KB Output is correct
17 Correct 13 ms 12152 KB Output is correct
18 Correct 13 ms 12152 KB Output is correct
19 Correct 13 ms 12152 KB Output is correct
20 Correct 12 ms 12152 KB Output is correct
21 Correct 13 ms 12152 KB Output is correct
22 Correct 13 ms 12152 KB Output is correct
23 Correct 13 ms 12152 KB Output is correct
24 Correct 13 ms 12152 KB Output is correct
25 Correct 13 ms 12152 KB Output is correct
26 Correct 13 ms 12152 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 72072 KB Output is correct
2 Correct 197 ms 72056 KB Output is correct
3 Correct 171 ms 72060 KB Output is correct
4 Correct 179 ms 75432 KB Output is correct
5 Correct 136 ms 70392 KB Output is correct
6 Correct 120 ms 70520 KB Output is correct
7 Correct 123 ms 70404 KB Output is correct
8 Correct 130 ms 70392 KB Output is correct
9 Correct 122 ms 69756 KB Output is correct
10 Correct 118 ms 68688 KB Output is correct
11 Correct 123 ms 71152 KB Output is correct
12 Correct 115 ms 68080 KB Output is correct
13 Correct 131 ms 71512 KB Output is correct
14 Correct 137 ms 69744 KB Output is correct
15 Correct 165 ms 71900 KB Output is correct
16 Correct 167 ms 71800 KB Output is correct
17 Correct 127 ms 71660 KB Output is correct
18 Correct 123 ms 71576 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 72416 KB Output is correct
2 Correct 206 ms 72376 KB Output is correct
3 Correct 297 ms 75384 KB Output is correct
4 Correct 178 ms 75376 KB Output is correct
5 Correct 154 ms 71172 KB Output is correct
6 Correct 154 ms 71144 KB Output is correct
7 Correct 155 ms 71160 KB Output is correct
8 Correct 154 ms 71132 KB Output is correct
9 Correct 122 ms 69756 KB Output is correct
10 Correct 143 ms 68848 KB Output is correct
11 Correct 152 ms 71792 KB Output is correct
12 Correct 154 ms 68964 KB Output is correct
13 Correct 264 ms 72192 KB Output is correct
14 Correct 312 ms 74232 KB Output is correct
15 Correct 194 ms 72696 KB Output is correct
16 Correct 190 ms 72696 KB Output is correct
17 Correct 157 ms 72440 KB Output is correct
18 Correct 166 ms 72376 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1177 ms 342640 KB Output is correct
2 Correct 1156 ms 342560 KB Output is correct
3 Correct 1473 ms 348392 KB Output is correct
4 Correct 1095 ms 348236 KB Output is correct
5 Correct 685 ms 336044 KB Output is correct
6 Correct 688 ms 335856 KB Output is correct
7 Correct 691 ms 335864 KB Output is correct
8 Correct 691 ms 335836 KB Output is correct
9 Correct 619 ms 326336 KB Output is correct
10 Correct 673 ms 336496 KB Output is correct
11 Correct 680 ms 336012 KB Output is correct
12 Correct 720 ms 336204 KB Output is correct
13 Correct 1016 ms 337392 KB Output is correct
14 Correct 1544 ms 349788 KB Output is correct
15 Correct 1022 ms 348144 KB Output is correct
16 Correct 986 ms 348240 KB Output is correct
17 Correct 706 ms 342868 KB Output is correct
18 Correct 710 ms 343088 KB Output is correct