Submission #1240896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240896		hengliao	Machine (IOI24_machine)	C++20	10 / 100	3 ms	440 KiB

machine

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef int ll;

namespace{
	const ll mxM=256;
}

vector<int> find_permutation(int n) {
	if(n%2==1){
		vll a(n);
		ll orgsum=0;
		for(ll i=0;i<n;i++){
			a[i]=i;
			orgsum^=a[i];
		}
		vll re=use_machine(a);
		ll sum=0;
		for(ll i=0;i<n;i++){
			sum^=re[i];
		}
		sum^=orgsum;
		vll b(n);
		for(ll i=0;i<n;i++){
			b[i]=re[i]^sum;
		}
		return b;
	}
	else{
		ll cnt1=n/2+1;
		ll cnt2=n/2-1;
		vll a(n);
		ll pt=0;
		vll id(mxM, -1);
		for(ll i=0;i<cnt1*2;i+=2){
			a[pt]=i;
			id[i]=pt;
			pt++;
		}
		for(ll i=1;i<cnt2*2;i+=2){
			a[pt]=i;
			id[i]=pt;
			pt++;
		}
		// for(ll i=0;i<n;i++){
		// 	cout<<a[i]<<' ';
		// }
		// cout<<'\n';
		vll re=use_machine(a);

		ll xx=-1;
		ll cnt=0;

		for(ll x=0;x<mxM;x++){
			bool good=1;
			for(ll i=0;i<n;i++){
				if(id[re[i]^x]==-1){
					good=0;
					break;
				}
			}
			if(good){
				xx=x;
				cnt++;
				// cout<<"x: "<<x<<'\n';
			}
		}

		assert(cnt==1);

		vll b(n);
		for(ll i=0;i<n;i++){
			b[i]=id[re[i]^xx];
		}
		return b;
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 19
• Subtask 4: 0 / 21
• Subtask 5: 10 / 10
• Subtask 6: 0 / 31