oj.uz

Submission #339680

# Submission time Handle Problem Language Result Execution time Memory
339680 2020-12-25T22:29:21 Z ogibogi2004 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 2 ms 492 KB 
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int pos[128];
void add(int l,int r,int n)
{
	if(l==r)return;
	string s="";
	for(int i=0;i<n;i++)
	{
		if(i<l||i>r)s+="1";
		else s+="0";
	}
	for(int i=l;i<=(l+r)/2;i++)
	{
		s[i]='1';
		add_element(s);
		s[i]='0';
	}
	add(l,(l+r)/2,n);
	add((l+r)/2+1,r,n);
}
void solve(int l,int r,int n,vector<int>v)
{
	if(l==r)
	{
		if(v.size()==0)cout<<"xd\n";
		pos[v[0]]=l;
		return;
	}
	string s="";
	for(int i=0;i<n;i++)
	{
		bool inv=0;
		for(int j=0;j<v.size();j++)
		{
			if(v[j]==i){inv=1;break;}
		}
		if(inv)s+="0";
		else s+="1";
	}
	vector<int>lh,rh;
	for(int i=0;i<v.size();i++)
	{
		s[v[i]]='1';
		if(check_element(s))
		{
			lh.push_back(v[i]);
		}
		else rh.push_back(v[i]);
		s[v[i]]='0';
	}
	int mid=(l+r)/2;
	solve(l,mid,n,lh);
	solve(mid+1,r,n,rh);
}
vector<int> restore_permutation(int n, int w, int r) {
    /*add_element("0");
    compile_set();
    check_element("0");
    return std::vector<int>();*/
   // cout<<"*\n";
    add(0,n-1,n);
   // cout<<"*\n";
    compile_set();
   // cout<<"*\n";
    vector<int>v;
    for(int i=0;i<n;i++)v.push_back(i);
    memset(pos,-1,sizeof(pos));
    solve(0,n-1,n,v);
   // cout<<"*\n";
    vector<int>ret;
    for(int i=0;i<n;i++)
    {
		ret.push_back(pos[i]);
		continue;
		for(int j=0;j<n;j++)
		{
			if(pos[j]==i){ret.push_back(j);break;}
		}
	}
	return ret;
}

Compilation message

messy.cpp: In function 'void solve(int, int, int, std::vector<int>)':
messy.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=0;j<v.size();j++)
      |               ~^~~~~~~~~
messy.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 8
2 Correct 1 ms 364 KB n = 8
3 Correct 1 ms 364 KB n = 8
4 Correct 1 ms 364 KB n = 8
5 Correct 1 ms 364 KB n = 8
6 Correct 1 ms 364 KB n = 8
7 Correct 1 ms 364 KB n = 8
8 Correct 1 ms 364 KB n = 8
9 Correct 1 ms 364 KB n = 8
10 Correct 1 ms 364 KB n = 8
11 Correct 1 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 364 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 32
2 Correct 1 ms 364 KB n = 32
3 Correct 1 ms 364 KB n = 32
4 Correct 1 ms 364 KB n = 32
5 Correct 1 ms 364 KB n = 32
6 Correct 1 ms 364 KB n = 32
7 Correct 1 ms 364 KB n = 32
8 Correct 1 ms 364 KB n = 32
9 Correct 1 ms 364 KB n = 32
10 Correct 1 ms 364 KB n = 32
11 Correct 1 ms 364 KB n = 32
12 Correct 1 ms 364 KB n = 32
13 Correct 1 ms 364 KB n = 32
14 Correct 1 ms 364 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 32
2 Correct 1 ms 364 KB n = 32
3 Correct 1 ms 364 KB n = 32
4 Correct 1 ms 364 KB n = 32
5 Correct 1 ms 364 KB n = 32
6 Correct 1 ms 364 KB n = 32
7 Correct 1 ms 364 KB n = 32
8 Correct 1 ms 364 KB n = 32
9 Correct 1 ms 364 KB n = 32
10 Correct 1 ms 364 KB n = 32
11 Correct 1 ms 364 KB n = 32
12 Correct 1 ms 364 KB n = 32
13 Correct 1 ms 364 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 364 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB n = 128
2 Correct 2 ms 492 KB n = 128
3 Correct 2 ms 492 KB n = 128
4 Correct 2 ms 492 KB n = 128
5 Correct 2 ms 492 KB n = 128
6 Correct 2 ms 492 KB n = 128
7 Correct 2 ms 492 KB n = 128
8 Correct 2 ms 492 KB n = 128
9 Correct 2 ms 492 KB n = 128
10 Correct 2 ms 492 KB n = 128
11 Correct 2 ms 492 KB n = 128
12 Correct 2 ms 492 KB n = 128
13 Correct 2 ms 492 KB n = 128
14 Correct 2 ms 492 KB n = 128
15 Correct 2 ms 492 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB n = 128
2 Correct 2 ms 492 KB n = 128
3 Correct 2 ms 492 KB n = 128
4 Correct 2 ms 492 KB n = 128
5 Correct 2 ms 492 KB n = 128
6 Correct 2 ms 492 KB n = 128
7 Correct 2 ms 492 KB n = 128
8 Correct 2 ms 492 KB n = 128
9 Correct 2 ms 492 KB n = 128
10 Correct 2 ms 492 KB n = 128
11 Correct 2 ms 492 KB n = 128
12 Correct 2 ms 492 KB n = 128
13 Correct 2 ms 492 KB n = 128
14 Correct 2 ms 492 KB n = 128
15 Correct 2 ms 492 KB n = 128