Submission #201187

#	Time	Username	Problem	Language	Result	Execution time	Memory
201187		Shelby	Zalmoxis (BOI18_zalmoxis)	C++11	0 / 100	1090 ms	10504 KiB

zalmoxis

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

int a[MAXN];
vector<int> sol;
vector<int> ans;
deque<int> d;
deque<int> r;
deque<int> pom;
int main()
{ int n,k,i;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{
    scanf("%d",&a[i]);

    r.push_back(a[i]);
}

d.push_back(30);

while(!r.empty())
{
    while(d.back()>r.back())
    {
        int x=d.back(); d.pop_back();

        if(x>1)
        {
            d.push_back(x-1);

            d.push_back(x-1);
        }
    }

    while(!r.empty() && d.back()<=r.back())
    {
        if(!r.empty() && d.back()==r.back())
        {
            sol.push_back(d.back());

            d.pop_back(); r.pop_back();
        }

        if(!r.empty() && d.back()<r.back())
        {
            sol.push_back(d.back());

            d.pop_back();
        }
    }
}

while(!d.empty())
{
    sol.push_back(d.back());

    d.pop_back();
}

//reverse(sol.begin(),sol.end());

for(i=0;i<sol.size();i++) pom.push_back(sol[i]);

int cnt=n+k-sol.size();

int poz=n;

if(cnt==0) ans.insert(ans.end(),sol.begin(),sol.end());

while(cnt>0)
{
    while(pom.back()==a[poz] && poz>0)
    {
        ans.push_back(a[poz]);

        poz--; pom.pop_back();
    }

    while(cnt>0 && pom.back()!=a[poz])
    {
        int x=pom.back(); pom.pop_back();

        deque<int> tmpl;

        tmpl.push_back(x);

        while(!tmpl.empty() && cnt>0)
        {
            if(!tmpl.empty() && tmpl.back()==1)
            {
                ans.push_back(1);

                tmpl.pop_back();
            }
            else
            {
                while(!tmpl.empty() && tmpl.back()!=1 && cnt>0)
                {
                    int y=tmpl.back(); tmpl.pop_back();

                    //cout << tmpl.size() << endl;

                    tmpl.push_back(y-1); tmpl.push_back(y-1);

                    cnt--;
                }

                while(cnt==0 && !tmpl.empty())
                {
                    ans.push_back( tmpl.back() );

                    tmpl.pop_back();
                }
            }

        }
    }


}
reverse(ans.begin(),ans.end());

for(i=0;i<ans.size();i++) printf("%d ",ans[i]);
    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:64:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<sol.size();i++) pom.push_back(sol[i]);
         ~^~~~~~~~~~~
zalmoxis.cpp:125:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<ans.size();i++) printf("%d ",ans[i]);
         ~^~~~~~~~~~~
zalmoxis.cpp:13:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d",&n,&k);
 ~~~~~^~~~~~~~~~~~~~
zalmoxis.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a[i]);
     ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70