Submission #1285018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285018		Faisal_Saqib	Unscrambling a Messy Bug (IOI16_messy)	C++17	49 / 100	2 ms	356 KiB

messy

// #pragma once

#include <bits/stdc++.h>
using namespace std;
void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

std::vector<int> restore_permutation(int n, int w, int r)
{
    // vector<int> ord;
    // for(int i=0;i<n;i++)
    // {
    //     ord.push_back(i);
    // }
    // random_shuffle(begin(ord),end(ord));
    string s(n,'0');
    vector<pair<int,string>> st;
    for(int i=0;i<n;i++)
    {
        s[i]='1';
        st.push_back({1,s});
        s[i]='0';
    }

    for(int i=0;i+1<n;i++)
    {
        s[i]='1';
        // s[ord[i]]='1';
        add_element(s);
    }
    compile_set();
    for(int i=0;i<n;i++)
    {
        s[i]='0';
    }
    // for(int m=1;m+1<(1<<n);m++) // exclude last
    // {
    //     string t;
    //     for(int i=0;i<n;i++)t+=char('0'+((m>>i)&1));
    //     int cnt=0;
    //     for(auto j:t)
    //     {
    //         if(j=='1')
    //         {
    //             cnt++;
    //         }
    //     }
    //     st.push_back({cnt,t});
    // }
    // sort(begin(st),end(st));

    vector<int> p(n+1,-1),done(n+2,0); // p[i] where i-th bit go
    set<int> cur;
    int as=0,askp=0;
    // for(auto typ:st)
    // cout<<"POS: ";
    // for(auto x:st)cout<<x.second<<' ';
    // cout<<endl;
    for(int tkp=0;tkp<st.size();tkp++)
    {
        auto typ=st[tkp];
        string t=typ.second;
        // if(done[typ.first])continue;
        askp++;
        if(check_element(t))
        {
            // cout<<"Found: ";
            // cout<<t<<endl;
            for(int k=0;k<n;k++)
            {
                if(t[k]!='1')continue;
                if(cur.find(k)==cur.end())
                {
                    // cout<<"As go : "<<as<<' '<<k<<endl;
                    p[as]=k;
                    cur.insert(k);
                    break;
                }
            }
            st.clear();
            s[p[as]]='1';
            for(int j=0;j<n;j++)
            {
                if(s[j]=='0')
                {
                    s[j]='1';
                    st.push_back({as+2,s});
                    s[j]='0';
                }
            }
            random_shuffle(begin(st),end(st));
            // cout<<"POS: ";
            // for(auto x:st)cout<<x.second<<' ';
            // cout<<endl;
            tkp=-1;
            as++;
        }
    }
    // cout<<"REad: ";
    // cout<<askp<<endl;
    vector<int> q(n,-1);
    for(int i=0;i<n;i++)
    {
        if(p[i]!=-1)
        {
            q[p[i]]=i;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(q[i]==-1)
        {
            q[i]=n-1;
        }
    }
    return q;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:92:27: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, __cxx11::basic_string<char> >*, vector<pair<int, __cxx11::basic_string<char> > > >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   92 |             random_shuffle(begin(st),end(st));
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from messy.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~
messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 0 / 21
• Subtask 5: 0 / 30