oj.uz

답안 #264200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
264200 2020-08-14T05:34:11 Z 반딧불(#5094) Teams (CEOI11_tea) C++17
50 / 100
 449 ms 59856 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<pair<int, int> > v;
int teamCnt;

vector<int> lim;
list<pair<int, int> > stk;

bool able(int sz){
    if(sz * teamCnt < n) return false;
    return true;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        v.push_back({x, i});
    }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    stk.push_back({0, 0 + v[0].first});
    for(int i=1; i<n; i++){
        while(!stk.empty() && stk.back().second > i + v[i].first) stk.pop_back();
        stk.push_back({i, i+v[i].first});
    }

    int pnt = 0;
    while(!stk.empty()){
        int i = stk.front().first;
        stk.pop_front();

        if(i + v[i].first <= n){
            int tmp = i + v[i].first;
            for(; pnt<=i; pnt++) tmp = max(tmp, pnt + v[pnt].first);
            teamCnt++;

            while(!stk.empty() && stk.front().first < tmp) stk.pop_front();
            if(!stk.empty()) pnt = stk.front().first;
        }
        else break;
    }

    printf("%d\n", teamCnt);

    int l = v[0].first, r = n, ans = v[0].first;
    while(l <= r){
        int m = (l+r)>>1;
        if(able(m)){
            ans = m;
            r = m-1;
        }
        else l = m+1;
    }

    int j = 0;
    for(int i=1; i<=teamCnt; i++){
        v.clear();
        lim.push_back(j);
        for(; j<i*ans && j<n-(teamCnt-i); j++);
    }
    lim.push_back(n);

    for(int i=teamCnt-1; i>=0; i--){
        while(lim[i] >= lim[i+1]) lim[i]--;
        while(v[lim[i]].first > lim[i+1]-lim[i]) lim[i]--;
    }

    for(int i=0; i<teamCnt; i++){
        printf("%d ", lim[i+1] - lim[i]);
        for(int j=lim[i]; j<lim[i+1]; j++) printf("%d ", v[j].second);
        puts("");
    }
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 200]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 512 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 4999]
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 3828 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 80005]
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 4328 KB Output is correct
2 Correct 35 ms 3692 KB Output is correct
3 Correct 43 ms 4328 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 307 ms 34896 KB Output is correct
2 Runtime error 255 ms 59856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 45908 KB Output is correct
2 Runtime error 250 ms 39516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 43600 KB Output is correct
2 Correct 339 ms 46416 KB Output is correct
3 Correct 404 ms 46416 KB Output is correct
4 Correct 446 ms 46416 KB Output is correct