Submission #108789

#	Time	Username	Problem	Language	Result	Execution time	Memory
108789		boatinw99	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	3 ms	640 KiB

messy

/**
 *    Author : boatinw99
 *    Date : 2.5.2019 8:40
 */
#include "messy.h"
#include<bits/stdc++.h>
using namespace std ;
#define mid (l+r>>1)
string s = "" ;
vector<int> ans ;
void mem(int l,int r,char val)
{
    for(int i=l;i<=r;i++)s[i]=val;
}
void add(int l,int r)
{
    if(l+1==r)return ;
    int len = r-l+1>>1;
    mem(l,mid,'1');
    for(int i=mid+1;i<=mid+len/2;i++)
    {
        s[i]='1';
        add_element(s);
        //cout << s << '\n' ;
        s[i]='0';
    }
    mem(l,mid,'0');
    /// right side
    mem(mid+1,r,'1');
    for(int i=mid-len/2+1;i<=mid;i++)
    {
        s[i]='1';
        add_element(s);
        //cout << s << '\n' ;
        s[i]='0';
    }
    mem(mid+1,r,'0');
    add(l,mid);
    add(mid+1,r);
}
void solve(int l,int r,vector<int> &vl,vector<int> &vr)
{
    if(l+1==r)
    {
        ans.push_back(*vl.begin());
        ans.push_back(*vr.begin());
        return ;
    }
    vector<int> dl,dr ;
    //for(auto it:vl)printf("vl %d \n",it);
    //for(auto it:vr)printf("vr %d \n",it);
    dl.clear();
    dr.clear();
    for(auto it:vr)s[it]='1';
    for(auto it:vl)
    {
        s[it]='1';
        bool chk = check_element(s);
        if(chk)dr.emplace_back(it);
        else dl.emplace_back(it);
        s[it]='0';
    }
    for(auto it:vr)s[it]='0';
    solve(l,mid,dl,dr);
    dl.clear();
    dr.clear();
    ///right side
    for(auto it:vl)s[it]='1';
    for(auto it:vr)
    {
        s[it]='1';
        bool chk = check_element(s);
        if(chk)dl.emplace_back(it);
        else dr.emplace_back(it);
        s[it]='0';
    }
    for(auto it:vl)s[it]='0';
    solve(mid+1,r,dl,dr);
    dl.clear();
    dr.clear();
}
vector<int> restore_permutation(int n,int w,int r)
{
    vector<int> ret(n);
    for(int i=0;i<n;i++)s+="0";
    for(int i=0;i<n/2;i++)
    {
        s[i]='1';
        add_element(s);
        s[i]='0';
    }
    add(0,n-1);

    compile_set();
    vector<int> vl,vr;
    for(int i=0;i<n;i++)
    {
        s[i]='1';
        bool chk = check_element(s);
        if(chk)vl.push_back(i);
        else vr.push_back(i);
        s[i]='0';
    }
    solve(0,n-1,vl,vr);
    int idx = 0 ;
    for(auto it:ans)ret[it]=idx++;
    return ret ;
}

Compilation message (stderr)

messy.cpp: In function 'void add(int, int)':
messy.cpp:18:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int len = r-l+1>>1;
               ~~~^~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:19:11: note: in expansion of macro 'mid'
     mem(l,mid,'1');
           ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:20:15: note: in expansion of macro 'mid'
     for(int i=mid+1;i<=mid+len/2;i++)
               ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:20:24: note: in expansion of macro 'mid'
     for(int i=mid+1;i<=mid+len/2;i++)
                        ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:27:11: note: in expansion of macro 'mid'
     mem(l,mid,'0');
           ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:29:9: note: in expansion of macro 'mid'
     mem(mid+1,r,'1');
         ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:30:15: note: in expansion of macro 'mid'
     for(int i=mid-len/2+1;i<=mid;i++)
               ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:30:30: note: in expansion of macro 'mid'
     for(int i=mid-len/2+1;i<=mid;i++)
                              ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:37:9: note: in expansion of macro 'mid'
     mem(mid+1,r,'0');
         ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:38:11: note: in expansion of macro 'mid'
     add(l,mid);
           ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:39:9: note: in expansion of macro 'mid'
     add(mid+1,r);
         ^~~
messy.cpp: In function 'void solve(int, int, std::vector<int>&, std::vector<int>&)':
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:64:13: note: in expansion of macro 'mid'
     solve(l,mid,dl,dr);
             ^~~
messy.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
messy.cpp:78:11: note: in expansion of macro 'mid'
     solve(mid+1,r,dl,dr);
           ^~~

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