Submission #229847

#	Time	Username	Problem	Language	Result	Execution time	Memory
229847		achibasadzishvili	Unscrambling a Messy Bug (IOI16_messy)	C++14	0 / 100	6 ms	384 KiB

messy

#include <bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
#include "messy.h"

vector<int> restore_permutation(int n, int w, int r){
    string s = "";
    srand(time(NULL));
    for(int i=1; i<=n; i++)
        s += '0';
    for(int i=0; i<n; i++){
        s[i] = '1';
        add_element(s);
    }
    ll sq = sqrt(n);
    s = "1";
    for(int i=1; i<n; i++)s += '0';
    for(int i=1; i<n; i++){
        s[i] = '1';
        add_element(s);
        s[i] = '0';
        if((i % sq) == 0){
            for(int j=i; j>=0; j--)
                s[j] = '1';
        }
    }
    compile_set();
    string a = "";
    for(int i=0; i<n; i++)
        a += '0';
    vector<ll>p;
    for(int i=0; i<n; i++)
        p.pb(0);
    vector<ll>k;
    for(int j=0; j<n; j++)
        if(a[j] == '0')
            k.pb(j);
    for(int i=0; i<n; i++){
        random_shuffle(k.begin() , k.end());
        random_shuffle(k.begin() , k.end());
        random_shuffle(k.begin() , k.end());
        random_shuffle(k.begin() , k.end());
        for(int ji=0; ji<k.size(); ji++){
            int j = k[ji];
            if(ji == k.size() - 1){
                k.pop_back();
                a[j] = '1';
                p[i] = j;
                break;
            }
            if(a[j] == '0'){
                a[j] = '1';
                if(check_element(a)){
                    p[i] = j;
                    swap(k[ji] , k[(int)k.size() - 1]);
                    k.pop_back();
                    break;
                }
                a[j] = '0';
            }
        }
        if((i % sq) == 0){
            k.clear();
            string po = "";
            for(int j=0; j<n; j++)
                po += '0';
            for(int j=0; j<=i; j++){
                po[p[j]] = '1';
            }
            for(int j=0; j<n; j++){
                if(po[j] == '1')continue;
                po[j] = '1';
                if(check_element(po)){
                    k.pb(j);
                }
                po[j] = '0';
            }
        }
    }
    
    vector<ll>ans;
    for(int i=0; i<n; i++)
        ans.pb(0);
    for(int i=0; i<p.size(); i++){
        ans[p[i]] = i;
    }
    
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int ji=0; ji<k.size(); ji++){
                       ~~^~~~~~~~~
messy.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ji == k.size() - 1){
                ~~~^~~~~~~~~~~~~~~
messy.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<p.size(); i++){
                  ~^~~~~~~~~

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