Submission #94200

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

messy

#include <vector>
#include <iostream>
#include <string>
#include "messy.h"
using namespace std;
string s,zr;
vector<int> perm,id;
void divide(int st,int dr)
{
    if(st+1==dr) return;
    s=zr;
    int m=(st+dr)/2;
    for(int i=st;i<dr;i++)
        s[i]='1';
    for(int i=st;i<m;i++)
    {
        s[i]='0';
        add_element(s);
        s[i]='1';
    }
    divide(st,m);
    divide(m,dr);
}
void rec(int st,int dr,vector<int> cand)
{
    //cand e unde pica elementele din [st;dr]
    if(st+1==dr)
    {
        perm[cand[0]]=st;
        return;
    }
    s=zr;
    vector<int> l,r;
    for(int i=0;i<cand.size();i++)
        s[cand[i]]='1';
    for(int i=0;i<cand.size();i++)
        {
            s[cand[i]]='0';
            if(check_element(s)) l.push_back(cand[i]);
            else r.push_back(cand[i]);
            s[cand[i]]='1';
        }
    int m=(st+dr)/2;
    rec(st,m,l);
    rec(m,dr,r);
}
vector<int> restore_permutation(int n, int w, int r) {
    for(int i=0;i<n;i++)
        zr+='0',perm.push_back(0);
    divide(0,n);
    compile_set();
    for(int i=0;i<n;i++)
        id.push_back(i);
    rec(0,n,id);
    return perm;
}

Compilation message (stderr)

messy.cpp: In function 'void rec(int, int, std::vector<int>)':
messy.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cand.size();i++)
                 ~^~~~~~~~~~~~
messy.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cand.size();i++)
                 ~^~~~~~~~~~~~

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