Submission #264280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
264280	2020-08-14T05:58:56 Z	반딧불(#5094)	Teams (CEOI11_tea)	C++17	60 / 100	1234 ms	59500 KB

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

void able(int sz){
    int pnt = 0;
    lim.clear();
    stk.clear();

    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});
    }

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

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

            while(!stk.empty() && stk.front().first < tmp) stk.pop_front();
            if(stk.front().first > lim.back() + sz)
                stk.push_front({lim.back() + sz, lim.back() + sz + v[lim.back() + sz].first});
            if(!stk.empty()) pnt = stk.front().first;
        }
        else break;
    }
    lim.push_back(n);

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

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 = max(v[0].first, (n + teamCnt - 1) / teamCnt), r = n, ans = v[0].first;
    while(l <= r){
        int m = (l+r)>>1;
        able(m);
        if(lim.size() == teamCnt + 1){
            ans = m; r = m-1; ansLim = lim;
        }
        else l = m+1;
    }

    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:92:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |         if(lim.size() == teamCnt + 1){
      |            ~~~~~~~~~~~^~~~~~~~~~~~~~
tea.cpp:88:66: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   88 |     int l = max(v[0].first, (n + teamCnt - 1) / teamCnt), r = n, ans = v[0].first;
      |                                                                  ^~~
tea.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	384 KB	Integer parameter [name=s_i] equals to 0, violates the range [1, 200]
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	512 KB	Integer parameter [name=s_i] equals to -119, violates the range [1, 4999]
2	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	5 ms	512 KB	Output is correct

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	81 ms	4268 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	4840 KB	Output is correct
2	Correct	75 ms	3944 KB	Output is correct
3	Correct	90 ms	4840 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	849 ms	37288 KB	Integer parameter [name=s_i] equals to 0, violates the range [1, 750013]
2	Halted	0 ms	0 KB	-

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1084 ms	48372 KB	Output is correct
2	Correct	1234 ms	59500 KB	Output is correct
3	Correct	1098 ms	49416 KB	Output is correct
4	Correct	1034 ms	43652 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1086 ms	45728 KB	Output is correct
2	Correct	412 ms	48600 KB	Output is correct
3	Correct	1104 ms	48748 KB	Output is correct
4	Correct	1194 ms	48876 KB	Output is correct