Submission #84328

#	Time	Username	Problem	Language	Result	Execution time	Memory
84328		zoooma13	Baloni (COCI15_baloni)	C++14	40 / 100	38 ms	1128 KiB

baloni

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 5003

int N;
vector <int> A;

int par[MAX_N];
int pat[MAX_N];
int bef[MAX_N];
bool bad[MAX_N];

int main()
{
    scanf("%d",&N); assert(N < MAX_N);
    A.resize(N ,0);
    for(int i=0; i<N; i++)
        scanf("%d",&A[i]);

    int Ans = 0;
    while(!A.empty())
    {
        memset(par ,0 ,sizeof par);
        memset(pat ,0 ,sizeof pat);
        memset(bef ,-1 ,sizeof bef);
        memset(bad ,0 ,sizeof bad);

        for(int i=0; i<A.size(); i++)
        {
            par[i] = bef[A[i]+1];
            pat[i] = (~bef[A[i]+1] ? pat[ bef[A[i]+1] ]+1 : 1);
            bef[A[i]] = i;
        }

        int now = max_element(pat ,pat+A.size()) - pat;
        for( ; ~now; now = par[now])
            bad[now] = 1;

        vector <int> NA;
        for(int i=0; i<A.size(); i++)
            if(!bad[i])
                NA.push_back(A[i]);

        A = NA;
        Ans++;
    }

    cout << Ans << endl;
}

Compilation message (stderr)

baloni.cpp: In function 'int main()':
baloni.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<A.size(); i++)
                      ~^~~~~~~~~
baloni.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<A.size(); i++)
                      ~^~~~~~~~~
baloni.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N); assert(N < MAX_N);
     ~~~~~^~~~~~~~~
baloni.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~

• Subtask 1: 40 / 100