oj.uz

Submission #64437

# Submission time Handle Problem Language Result Execution time Memory
64437 2018-08-04T13:17:21 Z Bodo171 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 534 ms 45356 KB 
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=1000*1000+5;
vector<int> trebuie[nmax];
int v[nmax],orig[nmax],act[nmax],niu[nmax],niuact[nmax];
int n,k,total,i,nr,newnr,j,p,idx;
void solve(int x)
{
    if(x==0)
    {
        cout<<x<<' ';
        return;
    }
    if(k>total)
    {
        total++;
        solve(x-1);
        solve(x-1);
    }
    else cout<<x<<' ';
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        orig[i]=v[i];
        act[i]=i;
    }
    nr=n;v[n+1]=-1;
    for(i=0;i<30;i++)
    {
        for(j=1;j<=nr;j++)
        {
            if(v[j]==i)
            {
                 p=j;
                 while(v[p]==i&&p<=nr)
                 {
                     p++;
                 }
                 p--;
                 if((p-j+1)&1)
                 {
                     trebuie[act[p]].push_back(i);
                     total++;
                 }
                 j=p;
            }
        }
        newnr=0;
        for(j=1;j<=nr;j++)
            if(v[j]==i)
        {
            p=j;
            while(v[p]==i&&p<=nr)
            {
                p++;
            }
            p--;
            for(idx=1;idx<=(p-j+2)/2;idx++)
            {
                ++newnr;
                niuact[newnr]=act[p];
                niu[newnr]=v[p]+1;
            }
            j=p;
        }
        else
        {
            ++newnr;
            niuact[newnr]=act[j];
            niu[newnr]=v[j];
        }
        nr=newnr;
        for(j=1;j<=nr;j++)
            v[j]=niu[j],act[j]=niuact[j];
    }
    for(i=1;i<=n;i++)
    {
        cout<<orig[i]<<' ';
        for(j=0;j<trebuie[i].size();j++)
            solve(trebuie[i][j]);
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<trebuie[i].size();j++)
                 ~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 44824 KB Output is correct
2 Correct 423 ms 44988 KB Output is correct
3 Correct 462 ms 45168 KB Output is correct
4 Correct 436 ms 45168 KB Output is correct
5 Correct 462 ms 45208 KB Output is correct
6 Correct 450 ms 45208 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 45236 KB Output is correct
2 Correct 434 ms 45236 KB Output is correct
3 Correct 425 ms 45236 KB Output is correct
4 Correct 449 ms 45356 KB Output is correct
5 Correct 459 ms 45356 KB Output is correct
6 Correct 494 ms 45356 KB Output is correct
7 Correct 425 ms 45356 KB Output is correct
8 Correct 439 ms 45356 KB Output is correct
9 Correct 382 ms 45356 KB Output is correct
10 Correct 242 ms 45356 KB Output is correct
11 Correct 303 ms 45356 KB Output is correct
12 Correct 111 ms 45356 KB Output is correct
13 Correct 203 ms 45356 KB Output is correct
14 Correct 116 ms 45356 KB Output is correct