Submission #316598

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
vector<int> res;
int N;
void add(int l,int r) {
	if(l == r) return;
	string s;
	for(int i = 0; i < N; i++) {
		if(i >= l && i <= r) s+='0';
		else s+='1';
	}

	int mid = l + r >> 1;

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

	add(l,mid);
	add(mid + 1, r);

}

void check(int l,int r,vector<int> v) {

	if(l == r) {
		res[l] = v[0];
		return;
	}

	string s;
	for(int i = 0; i < N; i++) s += '1';

	for(int i : v) s[i] = '0';
	int mid = l + r >> 1;

    vector<int> left,right;

    for(int i : v) {
    	s[i] = '1';
    	if(check_element(s)) left.push_back(i);
    	else right.push_back(i);
    	s[i] = '0';



    }

    check(l,mid,left);
    check(mid+1,r,right);


}
vector<int> restore_permutation(int n, int w, int r) {
	N = n;
    add(0,n-1);
    compile_set();

    vector<int> tmp(n);
    iota(tmp.begin(),tmp.end(),0);
    res.resize(n);
    check(0,n-1,tmp);

    vector<int> fr(n);
    for(int i = 0; i < N; i++) {
    	fr[res[i]] = i;
    }
    return fr;
    
    
}

Compilation message (stderr)

messy.cpp: In function 'void add(int, int)':
messy.cpp:14:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int mid = l + r >> 1;
      |            ~~^~~
messy.cpp: In function 'void check(int, int, std::vector<int>)':
messy.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |  int mid = l + r >> 1;
      |            ~~^~~

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