oj.uz

Submission #392742

# Submission time Handle Problem Language Result Execution time Memory
392742 2021-04-21T14:35:35 Z Ruxandra985 Teams (CEOI11_tea) C++14
30 / 100
 424 ms 39536 KB 
#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;
int dp[DIMN];
int mp[DIMN];
int tt[DIMN];

int w[DIMN] , poz[DIMN];

pair <int , int> v[DIMN];

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , now , st , dr , mid , elem , a , b;
    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);

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

    now = n;

    int maxi = now - tt[now];

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

        fprintf (fout,"%d " , now - w[st]);

        maxi = max(maxi , now - w[st]);

        while (now > w[st]){
            fprintf (fout,"%d ",v[now].second);
            now--;
        }

        fprintf (fout,"\n");

    }

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 26232 KB Output is correct
2 Correct 262 ms 28280 KB Output is correct
3 Correct 264 ms 29944 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 34244 KB Output is correct
2 Correct 424 ms 39536 KB Output is correct
3 Correct 340 ms 37672 KB Output is correct
4 Correct 326 ms 35268 KB Output is correct

Subtask #10
0 / 10.0

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