Submission #170388

#	Time	Username	Problem	Language	Result	Execution time	Memory
170388		arnold518	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	8 ms	632 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, W, R;
vector<int> ans, ans2;

void put(int s, int e)
{
    if(s+1==e) return;
    int i, j;
    int mid=s+e>>1;

    string S(N, '0');
    for(i=0; i<N; i++) if(!(s<=i && i<e)) S[i]='1';

    for(i=s; i<mid; i++)
    {
        S[i]='1';
        add_element(S);
        S[i]='0';
    }

    put(s, mid);
    put(mid, e);
}

void get(int s, int e, vector<int> cand)
{
    if(s+1==e)
    {
        ans[s]=cand[0];
        return;
    }
    int i, j;
    int mid=s+e>>1;

    string S(N, '0');
    for(i=0; i<N; i++) if(!binary_search(cand.begin(), cand.end(), i)) S[i]='1';

    vector<int> L, R;
    for(auto it : cand)
    {
        S[it]='1';
        if(check_element(S)) L.push_back(it);
        else R.push_back(it);
        S[it]='0';
    }

    get(s, mid, L);
    get(mid, e, R);
}

vector<int> restore_permutation(int _N, int _W, int _R)
{
    int i, j;
    N=_N; W=_W; R=_R;
    ans.resize(N);
    ans2.resize(N);

    vector<int> V;
    for(i=0; i<N; i++) V.push_back(i);

    put(0, N);
    compile_set();
    get(0, N, V);

    for(i=0; i<N; i++) ans2[ans[i]]=i;

    return ans2;
}

Compilation message (stderr)

messy.cpp: In function 'void put(int, int)':
messy.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=s+e>>1;
             ~^~
messy.cpp:15:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
messy.cpp: In function 'void get(int, int, std::vector<int>)':
messy.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=s+e>>1;
             ~^~
messy.cpp:39:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:60:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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