Submission #116457

#	Time	Username	Problem	Language	Result	Execution time	Memory
116457		davitmarg	Unscrambling a Messy Bug (IOI16_messy)	C++17	20 / 100	4 ms	1884 KiB

messy

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()

#ifndef  death
	#include "messy.h"
#endif


using namespace std;


#ifdef death

map<string, bool> USED;
vector<int> P;

void add_element(string s)
{
	string t = s;
	for (int i = 0; i < P.size(); i++)
		t[i] = s[P[i]];
	USED[t] = 1;
}

void compile_set()
{

}

bool check_element(string s)
{
	return USED[s];
}

#endif

int n;
string s;
vector<pair<string, pair<int, int>>> v;
vector<int> p;
void build(int l,int r)
{
	if (l >= r)
		return;
	int m = (l + r) / 2;
	for (int i = l; i <= m; i++)
		s[i] = '1';
	add_element(s);
	for (int i = l; i <= m; i++)
		for (int j = m+1; j <= r; j++)
		{
			swap(s[i],s[j]);
			v.PB(MP(s, MP(i, j)));
			swap(s[i],s[j]);
		}
	for (int i = l; i <= m; i++)
		s[i] = '0';
	build(l,m);
	build(m+1,r);
}

int Main()
{
	for (int i = 0; i < n; i++)
	{
		s += "0";
		p.PB(i);
	}
	build(0, n-1);
	compile_set();
	for(int i=0;i<v.size();i++)
		if (check_element(v[i].first))
		{
			swap(p[v[i].second.first], p[v[i].second.second]);
			break;
		}
	return 0;
}

vector<int> restore_permutation(int N, int w, int r)
{
	n = N;
	Main();
	return p;
}


#ifdef death

int main()
{
	int N, R, W;
	cin >> N >> W >> R;
	for (int i = 0; i < N; i++)
	{
		P.PB(0);
		cin >> P.back();
	}
	P = restore_permutation(N,W,R);
	for (int i = 0; i < N; i++)
		cout << P[i] << " ";
	cout << endl;
	return 0;
}

#endif

/*

8 0 0
1 0 2 3 4 5 6 7


*/

Compilation message (stderr)

messy.cpp: In function 'int Main()':
messy.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++)
              ~^~~~~~~~~

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