oj.uz

Submission #1099726

# Submission time Handle Problem Language Result Execution time Memory
1099726 2024-10-12T05:03:14 Z model_code Machine (IOI24_machine) C++17
100 / 100
 41 ms 724 KB 
// correct/sol.cpp

#include <bits/stdc++.h>
#include "machine.h"

using namespace std;

int ok(int n,int a,int b,int c)
{
	int co[8]={};
	for(int i=0;i<=n+2;i++)
	{
		if(i==a||i==b||i==c) continue;
		for(int j=0;j<8;j++)
			if(i&(1<<j)) co[j]++;
	}
	for(int i=0;i<8;i++)
		if(co[i]*2==n) return 0;
	return 1;
}

vector<int> ans[129];

vector<int> get(int n)
{
	if(ans[n].size()) return ans[n];
	vector<int> v;
	int got=0;
	for(int i=0;i<=n+2&&!got;i++)
	{
		for(int j=i+1;j<=n+2&&!got;j++)
		{
			for(int k=j+1;k<=n+2&&!got;k++)
			{
				if(ok(n,i,j,k))
				{
					got=1;
					for(int x=0;x<=n+2;x++)
					{
						if(x==i||x==j||x==k) continue;
						v.push_back(x);
					}
				}
			}
		}
	}
	ans[n]=v;
	return ans[n];
}

vector<int> find_permutation(int n)
{
	vector<int> v=get(n);
	int co[33]={};
	int co2[33]={};
	vector<int> ret=use_machine(v);
	for(int i:v)
		for(int j=0;j<30;j++)
			co[j]+=(i&(1<<j))>0;
	for(int i:ret)
		for(int j=0;j<30;j++)
			co2[j]+=(i&(1<<j))>0;
	int x=0;
	for(int i=0;i<30;i++)
		if(co[i]!=co2[i]) x|=(1<<i);
	for(int i=0;i<(int)ret.size();i++)
		ret[i]^=x;
	vector<int> perm;
	for(int i=0;i<(int)ret.size();i++)
	{
		perm.push_back(lower_bound(v.begin(),v.end(),ret[i])-v.begin());
	}
	return perm;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 7 ms 460 KB Output is correct
3 Correct 34 ms 452 KB Output is correct
4 Correct 13 ms 344 KB Output is correct
5 Correct 41 ms 476 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 5 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 22 ms 460 KB Output is correct
4 Correct 21 ms 344 KB Output is correct
5 Correct 25 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 600 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 21 ms 460 KB Output is correct
4 Correct 25 ms 340 KB Output is correct
5 Correct 26 ms 600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 27 ms 344 KB Output is correct
4 Correct 27 ms 452 KB Output is correct
5 Correct 31 ms 484 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 356 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 6 ms 452 KB Output is correct
7 Correct 9 ms 344 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 34 ms 344 KB Output is correct
4 Correct 28 ms 344 KB Output is correct
5 Correct 28 ms 468 KB Output is correct
6 Correct 7 ms 440 KB Output is correct
7 Correct 6 ms 600 KB Output is correct