Submission #711509

#	Time	Username	Problem	Language	Result	Execution time	Memory
711509		bin9638	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	580 KiB

messy

#include <bits/stdc++.h>

#ifndef SKY
#include "messy.h"
#endif // SKY
#include <cstdlib>

using namespace std;

#define ll long long
#define pb push_back
#define N 155
#define ii pair<int,int>
#define fs first
#define sc second

int n,LOG,ask[N];

//hàm thư viện
#ifdef SKY
    int per[N];
    map<string,int>mp;

    void compile_set()
    {

    }

    void add_element(string s)
    {
        string kq=s;
        for(int i=0;i<n;i++)
            kq[i]=s[per[i]];
        mp[kq]=1;
    }

    bool check_element(string s)
    {
        return(mp[s]==1);
    }
#endif // SKY

vector<ii>lis[N];
vector<vector<int>>pos[N];

void add()
{
    string s="";
    for(int i=0;i<n;i++)
        s.pb((char)(ask[i]+'0'));
    //cout<<s<<endl;
    add_element(s);
}

bool check()
{
    string s="";
    for(int i=0;i<n;i++)
        s.pb((char)(ask[i]+'0'));
    return check_element(s);
}

vector<int> restore_permutation(int cc, int w, int r)
{
    n=cc;
    #ifdef SKY
    for(int i=0;i<n;i++)
        cin>>per[i];
    #endif // SKY
    LOG=ceil(log2(n));
    lis[1].pb({0,n-1});
    for(int i=1;i<=LOG;i++)
        for(auto cc:lis[i])
            if(cc.fs==cc.sc)
            {
                lis[i+1].pb(cc);
            }else
            {
                int mid=(cc.fs+cc.sc)/2;
                lis[i+1].pb({cc.fs,mid});
                lis[i+1].pb({mid+1,cc.sc});
               // cout<<"cc";
            }
    for(int i=1;i<=LOG;i++)
        for(auto cc:lis[i])
            if(cc.fs<cc.sc)
            {
                memset(ask,0,sizeof(ask));
                for(auto u:lis[i])
                    if(u!=cc)
                    {
                        for(int j=u.fs;j<=u.sc;j++)
                            ask[j]=1;
                    }
                int l=cc.fs,r=cc.sc,mid=(l+r)/2;
                for(int j=l;j<=mid;j++)
                {
                    ask[j]=1;
                //cout<<l<<" "<<r<<" "<<i<<endl;
                    add();
                    ask[j]=0;
                }
            }
    compile_set();
    pos[1].pb({});
    for(int i=0;i<n;i++)
        pos[1][0].pb(i);
    for(int i=1;i<=LOG;i++)
        for(int j=0;j<lis[i].size();j++)
            if(lis[i][j].fs==lis[i][j].sc)
            {
                pos[i+1].pb(pos[i][j]);
            }else
            {
                int l=lis[i][j].fs,r=lis[i][j].sc,mid=(l+r)/2;
                memset(ask,0,sizeof(ask));
                for(int k=0;k<lis[i].size();k++)
                    if(k!=j)
                    {
                        for(auto vt:pos[i][k])
                            ask[vt]=1;
                    }
                vector<int>L,R;
                for(auto vt:pos[i][j])
                {
                    ask[vt]=1;
                    if(check())
                        L.pb(vt);
                            else R.pb(vt);
                    ask[vt]=0;
                }
              //  cout<<l<<" "<<r<<" "<<L.size()<<" "<<R.size()<<endl;
                pos[i+1].pb(L);
                pos[i+1].pb(R);
            }
 //  for(int i=0;i<n;i++)cout<<lis[LOG+1][i].fs<<endl;//" "<<pos[LOG+1][i].back()<<endl;
   // return {1};
    vector<int>kq(n);
    for(int i=0;i<n;i++)
        kq[pos[LOG+1][i].back()]=lis[LOG+1][i].fs;
    return kq;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n;
    cin>>n;
    vector<int>kq=restore_permutation(n,0,0);
    for(int i=0;i<n;i++)cout<<kq[i]<<" ";
}
#endif

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int j=0;j<lis[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
messy.cpp:117:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                 for(int k=0;k<lis[i].size();k++)
      |                             ~^~~~~~~~~~~~~~
messy.cpp:115:51: warning: unused variable 'mid' [-Wunused-variable]
  115 |                 int l=lis[i][j].fs,r=lis[i][j].sc,mid=(l+r)/2;
      |                                                   ^~~

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