Submission #1228304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228304		kl0989e	Machine (IOI24_machine)	C++20	100 / 100	71 ms	724 KiB

machine

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

vi find_permutation(int n) {
    if (n%2==0) {
        int num1,num2,num3;
        bool br=0;
        for (int i=0; i<=n+2 && (!br); i++) {
            for (int j=i+1; j<=n+2 && (!br); j++) {
                for (int m=j+1; m<=n+2; m++) {
                    set<vi> seen;
                    bool ok=1;
                    for (int k=0; k<256; k++) {
                        vi temp;
                        for (int l=0; l<=n+2; l++) {
                            if (l!=i && l!=j && l!=m) {
                                temp.pb(l^k);
                            }
                        }
                        sort(all(temp));
                        if (seen.find(temp)!=seen.end()) {
                            ok=0;
                            break;
                        }
                        seen.insert(temp);
                    }
                    if (ok) {
                        tie(num1,num2,num3)={i,j,m};
                        br=1;
                        break;
                    }
                }
            }
        }
        vi a;
        for (int i=0; i<=n+2; i++) {
            if (i!=num1 && i!=num2 && i!=num3) {
                a.pb(i);
            }
        }
        vi b=use_machine(a);
        for (int x=0; x<256; x++) {
            vi seen(256,0);
            bool ok=1;
            for (int i=0; i<n; i++) {
                if ((b[i]^x)>n+2 || (b[i]^x)==num1 || (b[i]^x)==num2 || (b[i]^x)==num3) {
                    ok=0;
                    break;
                }
                if (seen[b[i]^x]) {
                    ok=0;
                    break;
                }
                seen[b[i]^x]=1;
            }
            if (ok) {
                for (int i=0; i<n; i++) {
                    b[i]^=x;
                    b[i]-=(b[i]>=num1)+(b[i]>=num2)+(b[i]>=num3);
                }
                break;
            }
        }
        return b;
    }
    vi a(n);
    iota(all(a),0);
    vi b=use_machine(a);
    for (int x=0; x<256; x++) {
        vi seen(256,0);
        bool ok=1;
        for (int i=0; i<n; i++) {
            if ((b[i]^x)>=n) {
                ok=0;
                break;
            }
            if (seen[b[i]^x]) {
                ok=0;
                break;
            }
            seen[b[i]^x]=1;
        }
        if (ok) {
            for (int i=0; i<n; i++) {
                b[i]^=x;
            }
            break;
        }
    }
    return b;
}

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