Submission #102592

#	Time	Username	Problem	Language	Result	Execution time	Memory
102592		daniel920712	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	588 KiB

messy

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include "messy.h"
using namespace std;

string all1;
string all2;
string all;
string temp;
vector < int >t1;
vector < int >t2;
vector < int > restore_permutation(int n, int w, int r)
{
    vector < int > ans;

    int i,j,x=0;
    for(i=0;i<n;i++) ans.push_back(0);
    for(i=0;i<n;i++)
    {
        all+='0';
        all1+='0';
        all2+='0';
        temp+='0';
    }
    for(i=n/2;i<n;i++)
    {
        all[i]='1';
        add_element(all);
        //cout<< all << "\n";
        all[i]='0';
    }
    //cout << "\n" ;
    for(i=n/4;i>=1;i/=2)
    {

        for(j=0;j<n;j++) all[j]='0';
        for(j=0;j<i*2;j++) all[j]='1';
        for(j=n/2;j<n;j++)
        {
            if(j&i)
            {
                all[j]='1';
                add_element(all);
                //cout<< all << "\n";
                all[j]='0';
            }
        }

        for(j=0;j<n;j++) all[j]='0';
        for(j=0;j<i*2;j++) all[n/2+j]='1';
        for(j=0;j<n/2;j++)
        {
            if(j&i)
            {
                all[j]='1';
                add_element(all);
                //cout<< all << "\n";
                all[j]='0';
            }
        }

        //
        //cout<<"\n";


    }
    compile_set();
    for(i=0;i<n;i++) all[i]='0';
    for(i=0;i<n;i++)
    {
        all[i]='1';
        if(check_element(all)) ans[i]+=n/2;
        all[i]='0';
    }
    for(i=n/4;i>=1;i/=2)
    {
        //printf("%d\n",i);

        for(j=0;j<n;j++) all1[j]='0';
        for(j=0;j<n;j++) if(ans[j]==n/2) all1[j]='1';

        for(j=0;j<n;j++) all2[j]='0';
        for(j=0;j<n;j++) if(ans[j]==0) all2[j]='1';

        t1.clear();
        t2.clear();
        for(j=0;j<n;j++) if(ans[j]!=n/2&&ans[j]<n/2) t1.push_back(j);
        for(j=0;j<n;j++) if(ans[j]!=0&&ans[j]>=n/2) t2.push_back(j);

        for(auto j:t1)
        {
            all1[j]='1';
            if(check_element(all1)) ans[j]+=i;
            all1[j]='0';
        }
        for(auto j:t2)
        {
            all2[j]='1';
            if(check_element(all2)) ans[j]+=i;
            all2[j]='0';
        }
    }
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:18:13: warning: unused variable 'x' [-Wunused-variable]
     int i,j,x=0;
             ^

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