Submission #392150

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392150	2021-04-20T14:55:17 Z	nicolaalexandra	Teams (CEOI11_tea)	C++14	70 / 100	2500 ms	115588 KB

#include <bits/stdc++.h>
#define DIM 1000010
#define DIMBUFF 20000000
#define INF 2000000000
using namespace std;

pair <int,int> v[DIM],aint[DIM*4];
vector <int> sol[DIM],events[DIM];
vector <pair<int,int> > s;
int t[DIM],dp[DIM];
char buff[DIMBUFF];
int n,i,j,k,ans,poz,pos;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = make_pair (-1,st);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = aint[nod<<1];
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].first = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    if (aint[nod<<1].first > aint[(nod<<1)|1].first)
        aint[nod] = aint[nod<<1];
    else aint[nod] = aint[(nod<<1)|1];
}

void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        if (aint[nod].first > ans)
            ans = aint[nod].first, poz = aint[nod].second;
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

int verif (int lg){
    int i;

    for (i=0;i<=n;i++)
        dp[i] = -1;
    dp[0] = 0;

    build (1,0,n);

    for (i=1;i<=n;i++){
        for (auto it : events[i])
            update (1,0,n,it,dp[it]);

        ans = -1, poz = 0;
        query (1,0,n,max(0,i-lg),i-1);

        if (ans != -1){
            dp[i] = ans + 1;
            t[i] = poz;
        }
    }

    return dp[n];
}
int get_nr (){
    int semn = 1;
    while (!(buff[pos] >= '0' && buff[pos] <= '9')){
        if (buff[pos] == '-')
            semn = -1;
        pos++;
    }

    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr * semn;

}

int main (){

    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");

    FILE *fin = stdin;
    FILE *fout = stdout;
    fread (buff,1,DIMBUFF,fin);

    n = get_nr();
    for (i=1;i<=n;i++){
        v[i].first = get_nr();
        v[i].second = i;
    }

    sort (v+1,v+n+1);
    reverse (v+1,v+n+1);

    /// dp[i] - nr maxim de secv in care pot imparti sirul si care e dimensiunea maxima minima

    /// cand incepe sa aiba influenta un dp?
    for (i=1;i<=n;++i)
        events[i + v[i].first - 1].push_back(i-1);

    int maxi = verif (n);

    int st = 1, dr = n, lg;
    while (st <= dr){
        int mid = (st+dr)>>1;

        if (verif(mid) == maxi){ /// incerc o lungime mai mica
            dr = mid-1;
            lg = mid;
        } else st = mid+1;
    }

    verif (lg);

    int x = n;
    while (x > 0){

        ++k;
        for (i=t[x]+1;i<=x;++i)
            sol[k].push_back(v[i].second);

        x = t[x];
    }

    fprintf(fout,"%d\n",k);

    for (i=1;i<=k;++i){
        fprintf(fout,"%d ",sol[i].size());
        for (auto it : sol[i])
            fprintf(fout,"%d ",it);
        fprintf(fout,"\n");
    }


    return 0;
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:146:24: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  146 |         fprintf(fout,"%d ",sol[i].size());
      |                       ~^   ~~~~~~~~~~~~~
      |                        |              |
      |                        int            std::vector<int>::size_type {aka long unsigned int}
      |                       %ld
tea.cpp:102:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  102 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~
tea.cpp:131:11: warning: 'lg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |     verif (lg);
      |     ~~~~~~^~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47180 KB	Output is correct
2	Correct	30 ms	47308 KB	Output is correct
3	Correct	30 ms	47312 KB	Output is correct
4	Correct	30 ms	47312 KB	Output is correct
5	Correct	30 ms	47308 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47308 KB	Output is correct
2	Correct	29 ms	47228 KB	Output is correct
3	Correct	28 ms	47340 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47252 KB	Output is correct
2	Correct	30 ms	47292 KB	Output is correct
3	Correct	30 ms	47228 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	47644 KB	Output is correct
2	Correct	50 ms	47612 KB	Output is correct
3	Correct	51 ms	47684 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	47636 KB	Output is correct
2	Correct	48 ms	47660 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	475 ms	54280 KB	Output is correct
2	Correct	508 ms	54224 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	583 ms	54832 KB	Output is correct
2	Correct	453 ms	53996 KB	Output is correct
3	Correct	552 ms	54852 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2575 ms	102472 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2582 ms	115588 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2589 ms	112708 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-