oj.uz

Submission #821353

# Submission time Handle Problem Language Result Execution time Memory
821353 2023-08-11T09:28:20 Z PVM_pvm Watermelon (INOI20_watermelon) C++17
7 / 100
 2000 ms 5096 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAXX 100007
#define MAXN 13
long long b[MAXX],n,k;
struct perm
{
    long long ch[MAXN];
    perm(long long a[])
    {
        for (long long q=1;q<=n;q++) ch[q]=a[q];
    }
    void show()
    {
        //cout<<"P:";
        for (long long q=1;q<=n;q++) cout<<ch[q]<<" ";
        cout<<"\n";
    }
};
vector<perm> ans;
long long cur[MAXN],sb[MAXN];
bool dt[MAXN];
void check()
{
    for (long long q=1;q<=n;q++) sb[q]=-1;
    for (long long q=1;q<=n;q++) dt[q]=false;
    for (long long tm=1;true;tm++)
    {
        bool smyrt=false;
        for (long long q=1;q<=n;q++)
        {
            if (dt[q]) continue;
            long long next=q+1;
            for (next=q+1;next<=n;next++)
            {
                if (!dt[next]) break;
            }
            if (next>n) break;
            if (cur[next]>cur[q])
            {
                dt[q]=true;
                smyrt=true;
                sb[q]=tm;
            }
        }
        if (!smyrt) break;
    }
    bool pr=true;
    for (long long q=1;q<=n;q++)
    {
        if (sb[q]!=b[q]) pr=false;
    }
    if (pr)
    {
        perm spr(cur);
        ans.push_back(spr);
    }
}
long long ind[MAXN];
long long ind2[MAXN];
bool cmp(perm &a, perm &b){
    for (long long q=1;q<=n;q++)
    {
        ind[a.ch[q]] = q;
        ind2[b.ch[q]] = q;
    }
    for (long long q=1;q<=n;q++)
    {
        if (ind[q] < ind2[q]) return 1;
        if (ind[q] > ind2[q]) return 0;
    }
    return 0;
}
struct node
{
    long long sm;
    long long pos;
    long long lz;
} seg[4*MAXX];
void Initialise(long long ind, long long l, long long r)
{
    if (l==r)
    {
        if (b[l]==-1)
        {
            seg[ind].sm=n*2;
        }
        else
        {
            seg[ind].sm=b[l];
        }
        seg[ind].pos=l;
        seg[ind].lz=0;
        return;
    }
    long long mid=(l+r)/2;
    Initialise(ind*2,l,mid);
    Initialise(ind*2+1,mid+1,r);
    if (seg[ind*2].sm<=seg[ind*2+1].sm)
    {
        seg[ind].sm=seg[ind*2].sm;
        seg[ind].pos=seg[ind*2].pos;
    }
    else
    {
        seg[ind].sm=seg[ind*2+1].sm;
        seg[ind].pos=seg[ind*2+1].pos;
    }
    seg[ind].lz=0;
}
void Push(long long ind, long long l, long long r)
{
    if (seg[ind].lz==0) return;
    seg[ind].sm-=seg[ind].lz;
    if (l!=r)
    {
        seg[ind*2].lz+=seg[ind].lz;
        seg[ind*2+1].lz+=seg[ind].lz;
    }
    seg[ind].lz=0;
}
void Update(long long ind, long long l, long long r, long long ql, long long qr)
{
    Push(ind,l,r);
    if (l>=ql && r<=qr)
    {
        seg[ind].lz++;
        Push(ind,l,r);
        return;
    }
    long long mid=(l+r)/2;
    if (ql<=mid) Update(ind*2,l,mid,ql,qr);
    if (qr>=mid+1) Update(ind*2+1,mid+1,r,ql,qr);
    Push(ind*2,l,mid);
    Push(ind*2+1,mid+1,r);
    if (seg[ind*2].sm<=seg[ind*2+1].sm)
    {
        seg[ind].sm=seg[ind*2].sm;
        seg[ind].pos=seg[ind*2].pos;
    }
    else
    {
        seg[ind].sm=seg[ind*2+1].sm;
        seg[ind].pos=seg[ind*2+1].pos;
    }
}
void UpdateCh(long long ind, long long l, long long r, long long pos)
{
    Push(ind,l,r);
    if (l==r && l==pos)
    {
        seg[ind].sm=n*2;
        seg[ind].pos=l;
        seg[ind].lz=0;
        return;
    }
    long long mid=(l+r)/2;
    if (pos<=mid) UpdateCh(ind*2,l,mid,pos);
    if (pos>=mid+1) UpdateCh(ind*2+1,mid+1,r,pos);
    Push(ind*2,l,mid);
    Push(ind*2+1,mid+1,r);
    if (seg[ind*2].sm<=seg[ind*2+1].sm)
    {
        seg[ind].sm=seg[ind*2].sm;
        seg[ind].pos=seg[ind*2].pos;
    }
    else
    {
        seg[ind].sm=seg[ind*2+1].sm;
        seg[ind].pos=seg[ind*2+1].pos;
    }
}
long long ansk[MAXX];
long long pr1[MAXX];
long long chb[MAXX];
bool finalcheck()
{
    stack<pair<long long,long long>> st;
    chb[n]=-1;
    st.push({ansk[n],n});
    for (long long q=n-1;q>=1;q--)
    {
        while (true)
        {
            if (st.empty())
            {
                chb[q]=-1;
                st.push({ansk[q],q});
                break;
            }
            long long chislo = st.top().first;
            long long pos = st.top().second;
            if (ansk[q]>chislo)
            {
                st.pop();
                continue;
            }
            chb[q]=pos-q;
            st.push({ansk[q],q});
            break;
        }
    }
    for (long long q=1;q<=n;q++)
    {
        if (chb[q]!=b[q]) return false;
    }
    return true;
}
int main()
{
    cin>>n>>k;
    if (k!=1)
    {
        for (long long q=1;q<=n;q++) cin>>b[q];
        for (long long q=1;q<=n;q++) cur[q]=q;
        check();
        while (next_permutation(cur+1,cur+n+1)) check();
        sort(ans.begin(),ans.end(),cmp);
        if (k<ans.size()) ans[k-1].show();
        else cout<<"-1\n";
    }
    else
    {
        for (long long q=1;q<=n;q++) cin>>b[q];
        /*if (b[n]!=-1)
        {
            cout<<"-1\n";
            return 0;
        }*/
        long long br2=0;
        for (long long q=1;q<=n;q++)
        {
            if (b[q]!=-1) br2++;
        }
        pr1[0]=0;
        for (long long q=1;q<=n;q++)
        {
            if (b[q-1]==-1) pr1[q]=q-1;
            else pr1[q]=pr1[q-1];
        }
        Initialise(1,1,n);
        long long tm=0;
        for (tm=1;tm<n;tm++)
        {
            Push(1,1,n);
            long long sm=seg[1].sm;
            long long pos=seg[1].pos;
            if (sm!=1) break;
            ansk[pos]=tm;
            UpdateCh(1,1,n,pos);
            if (pos!=1) Update(1,1,n,pr1[pos]+1,pos-1);
        }
        /*if (tm-1 != br2)
        {
            cout<<"-1\n";
            return 0;
        }*/
        tm=n;
        for (long long q=1;q<=n;q++)
        {
            if (ansk[q]==0)
            {
                ansk[q]=tm;
                tm--;
            }
        }
        if (finalcheck())
        {
            for (long long q=1;q<=n;q++)
            {
                cout<<ansk[q]<<" ";
            }
            cout<<"\n";
        }
        else
        {
            cout<<"-1\n";
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:219:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<perm>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |         if (k<ans.size()) ans[k-1].show();
      |             ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 392 ms 600 KB Output is correct
13 Correct 388 ms 764 KB Output is correct
14 Correct 383 ms 400 KB Output is correct
15 Correct 376 ms 560 KB Output is correct
16 Correct 385 ms 548 KB Output is correct
17 Correct 375 ms 472 KB Output is correct
18 Correct 36 ms 404 KB Output is correct
19 Correct 386 ms 292 KB Output is correct
20 Correct 388 ms 296 KB Output is correct
21 Correct 377 ms 296 KB Output is correct
22 Correct 389 ms 296 KB Output is correct
23 Correct 399 ms 332 KB Output is correct
24 Correct 376 ms 300 KB Output is correct
25 Correct 385 ms 296 KB Output is correct
26 Correct 377 ms 292 KB Output is correct
27 Correct 387 ms 332 KB Output is correct
28 Correct 380 ms 292 KB Output is correct
29 Correct 382 ms 432 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 3 ms 340 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 392 ms 600 KB Output is correct
13 Correct 388 ms 764 KB Output is correct
14 Correct 383 ms 400 KB Output is correct
15 Correct 376 ms 560 KB Output is correct
16 Correct 385 ms 548 KB Output is correct
17 Correct 375 ms 472 KB Output is correct
18 Correct 36 ms 404 KB Output is correct
19 Correct 386 ms 292 KB Output is correct
20 Correct 388 ms 296 KB Output is correct
21 Correct 377 ms 296 KB Output is correct
22 Correct 389 ms 296 KB Output is correct
23 Correct 399 ms 332 KB Output is correct
24 Correct 376 ms 300 KB Output is correct
25 Correct 385 ms 296 KB Output is correct
26 Correct 377 ms 292 KB Output is correct
27 Correct 387 ms 332 KB Output is correct
28 Correct 380 ms 292 KB Output is correct
29 Correct 382 ms 432 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 3 ms 340 KB Output is correct
34 Execution timed out 2073 ms 212 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 392 ms 600 KB Output is correct
13 Correct 388 ms 764 KB Output is correct
14 Correct 383 ms 400 KB Output is correct
15 Correct 376 ms 560 KB Output is correct
16 Correct 385 ms 548 KB Output is correct
17 Correct 375 ms 472 KB Output is correct
18 Correct 36 ms 404 KB Output is correct
19 Correct 386 ms 292 KB Output is correct
20 Correct 388 ms 296 KB Output is correct
21 Correct 377 ms 296 KB Output is correct
22 Correct 389 ms 296 KB Output is correct
23 Correct 399 ms 332 KB Output is correct
24 Correct 376 ms 300 KB Output is correct
25 Correct 385 ms 296 KB Output is correct
26 Correct 377 ms 292 KB Output is correct
27 Correct 387 ms 332 KB Output is correct
28 Correct 380 ms 292 KB Output is correct
29 Correct 382 ms 432 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 3 ms 340 KB Output is correct
34 Execution timed out 2073 ms 212 KB Time limit exceeded
35 Halted 0 ms 0 KB -