Submission #264063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
264063	2020-08-14T04:56:52 Z	문홍윤(#5092)	Teams (CEOI11_tea)	C++17	100 / 100	652 ms	143456 KB

#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int inf=1e9;

int n, dp[1000010], fr[1000010];
pii arr[1000010];
vector<int> vc[1000010];

pii tree[1000010];
pii qu(int i){
    if(i<0)return mp(-inf, -inf);
    pii ans=mp(0, 0);
    while(i){
        ans=max(ans, tree[i]);
        i-=(i&-i);
    }
    return ans;
}
void upd(int i, pii num){
    while(i<=1000000){
        tree[i]=max(tree[i], num);
        i+=(i&-i);
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i].F);
        arr[i].S=i;
    }
    sort(arr+1, arr+n+1);
    for(int i=1; i<=n; i++){
        for(auto j:vc[i])upd(j, mp(dp[j], j));
        pii tmp=qu(i-arr[i].F);
        fr[i]=tmp.S;
        dp[i]=tmp.F+1;
        if(2*i-fr[i]<=n)vc[2*i-fr[i]].eb(i);
    }
    vector<vector<int> > ans;
    int nw=n;
    while(nw){
        vector<int> tmp;
        for(int i=nw; i>fr[nw]; i--)tmp.eb(arr[i].S);
        ans.eb(tmp);
        nw=fr[nw];
    }
    printf("%d\n", ans.size());
    for(auto i:ans){
        printf("%d ", i.size());
        for(auto j:i)printf("%d ", j);
        puts("");
    }
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:53:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
   53 |     printf("%d\n", ans.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<std::vector<int> >::size_type {aka long unsigned int}
      |             %ld
tea.cpp:55:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   55 |         printf("%d ", i.size());
      |                 ~^    ~~~~~~~~
      |                  |          |
      |                  int        std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
tea.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%d", &arr[i].F);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	17 ms	23936 KB	Output is correct
3	Correct	19 ms	23936 KB	Output is correct
4	Correct	15 ms	23936 KB	Output is correct
5	Correct	18 ms	23896 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23936 KB	Output is correct
2	Correct	19 ms	23936 KB	Output is correct
3	Correct	17 ms	23936 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23936 KB	Output is correct
2	Correct	18 ms	23936 KB	Output is correct
3	Correct	19 ms	23936 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	24064 KB	Output is correct
2	Correct	17 ms	24224 KB	Output is correct
3	Correct	20 ms	24320 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	24064 KB	Output is correct
2	Correct	16 ms	24064 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	27548 KB	Output is correct
2	Correct	55 ms	29048 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	28536 KB	Output is correct
2	Correct	53 ms	29048 KB	Output is correct
3	Correct	59 ms	28664 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	397 ms	72224 KB	Output is correct
2	Correct	435 ms	73952 KB	Output is correct
3	Correct	395 ms	65988 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	508 ms	80532 KB	Output is correct
2	Correct	652 ms	143456 KB	Output is correct
3	Correct	563 ms	89992 KB	Output is correct
4	Correct	509 ms	80648 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	466 ms	55976 KB	Output is correct
2	Correct	312 ms	54160 KB	Output is correct
3	Correct	527 ms	89360 KB	Output is correct
4	Correct	577 ms	87640 KB	Output is correct