oj.uz

답안 #392893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392893 2021-04-22T07:46:53 Z Ruxandra985 Teams (CEOI11_tea) C++14
100 / 100
 912 ms 37960 KB 
#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;
int dp[DIMN];
int mp[DIMN];
int tt[DIMN];

struct idk{

    int ech , ok , sz , fth;

} dp2[5010];

int w[DIMN] , poz[DIMN];

pair <int , int> v[DIMN];

FILE *fin = stdin;
FILE *fout = stdout;

int ok (int maxi , int n , int ok){

    int now , a , b , st , dr , mid;

    now = n;

    while (now){ /// nu pare o idee buna ce fac....

        a = max(0 , now - maxi); /// ma asigur ca v2 nu e -1
        /// cea mai mica echipa posibila ar fi de v[now].first
        b = now - v[now].first;

        while (tt[b] == -1)
            b--;

        /// a <= b

        if (a > b)
            swap(a , b);

        a = poz[a];

        b = poz[b];

        st = a;
        dr = b;
        while (st <= dr){
            mid = (st + dr)/2;

            if (dp[w[mid]] + 1 == dp[now])
                dr = mid - 1;
            else st = mid + 1;
        }

        if (ok){
            fprintf (fout,"%d " , now - w[st]);
        }

        if (now - w[st] > maxi)
            return 0;

        while (now > w[st]){
            if (ok){
                fprintf (fout,"%d ",v[now].second);
                //printf ("%d ",v[now].first);
            }
            now--;
        }
        if (ok){
            fprintf (fout,"\n");
            //printf ("\n");
        }

    }

    return 1;


}

int main()
{
    int n , i , st , dr , mid , elem , j , now;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i].first);
        v[i].second = i;
    }
    sort (v + 1 , v + n + 1);

    if (n <= 5000){

        dp2[0].ok = 1;

        for (i = 1 ; i <= n ; i++){

            for (j = i - v[i].first ; j >= 0 ; j--){

                if (!dp2[j].ok)
                    continue;

                if (dp2[j].ech + 1 > dp2[i].ech){

                    dp2[i].ech = dp2[j].ech + 1;
                    dp2[i].ok = 1;
                    dp2[i].sz = max(i - j , dp2[j].sz);
                    dp2[i].fth = j;

                }
                else if (dp2[j].ech + 1 == dp2[i].ech && max(i - j , dp2[j].sz) < dp2[i].sz){

                    dp2[i].ech = dp2[j].ech + 1;
                    dp2[i].ok = 1;
                    dp2[i].sz = max(i - j , dp2[j].sz);
                    dp2[i].fth = j;

                }

            }

        }

        fprintf (fout,"%d\n" , dp2[n].ech);

        now = n;

        while (now){

            fprintf (fout,"%d ", now - dp2[now].fth);

            for (i = now ; i > dp2[now].fth ; i--)
                fprintf (fout,"%d ",v[i].second);

            fprintf (fout,"\n");

            now = dp2[now].fth;

        }


        return 0;
    }

    elem = 0;

    for (i = 1 ; i <= n ; i++){

        if (i - v[i].first < 0){
            dp[i] = -2000000000;
            mp[i] = mp[i - 1];
            tt[i] = -1;
        }
        else {
            dp[i] = mp[i - v[i].first] + 1;
            w[++elem] = i;
            poz[i] = elem;
            tt[i] = i - v[i].first;
            mp[i] = max(mp[i - 1] , dp[i]);
        }

    }

    fprintf (fout,"%d\n" , dp[n]);

    st = v[n].first;
    dr = n;
    while (st <= dr){

        mid = (st + dr)/2;

        if (ok(mid , n , 0))
            dr = mid - 1; /// merge, cauti mai mic
        else st = mid + 1;


    }

    /// solutia e st (dim minima a echipei maxime)

    //printf ("%d ",st);

    ok(st , n , 1);


    return 0;
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:84:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     fscanf (fin,"%d",&n);
      |     ~~~~~~~^~~~~~~~~~~~~
tea.cpp:86:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |         fscanf (fin,"%d",&v[i].first);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 460 KB Output is correct
2 Correct 15 ms 564 KB Output is correct
3 Correct 17 ms 460 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 11 ms 444 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 3256 KB Output is correct
2 Correct 28 ms 3208 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 3532 KB Output is correct
2 Correct 28 ms 2976 KB Output is correct
3 Correct 32 ms 3576 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 267 ms 26264 KB Output is correct
2 Correct 306 ms 26436 KB Output is correct
3 Correct 271 ms 25940 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 362 ms 34408 KB Output is correct
2 Correct 912 ms 37960 KB Output is correct
3 Correct 411 ms 35040 KB Output is correct
4 Correct 335 ms 30788 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 31720 KB Output is correct
2 Correct 288 ms 27124 KB Output is correct
3 Correct 364 ms 35012 KB Output is correct
4 Correct 382 ms 35012 KB Output is correct