Submission #1206469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206469		dosts	Machine (IOI24_machine)	C++20	69 / 100	3 ms	444 KiB

machine

#include "machine.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;



int compat(vi a,vi b) {
    int xr = 0;
    for (auto it : a) xr^=it;
    for (auto it : b) xr^=it;
    vi v1;
    for (auto it : a) v1.push_back(it^xr);
    sort(all(v1));
    if (v1 == b) return xr;
    return -1;
}
std::vector<int> find_permutation(int N) {
  if (N%2) {
    vi ask;
    for (int i = 0;i<N;i++) ask.push_back(i);
    vi A = use_machine(ask);
    int xr = 0;
    for (int i = 0;i<N;i++) xr^=i;
    for (int i = 0;i<N;i++) xr^=A[i];
    vi ans(N);
    for (int i = 0;i<N;i++) ans[i] = A[i]^xr;
    return ans;
  }
  else {
    int pw = 1;
    while (pw < N) pw*=2;
    vi ask;
    for (int i = 0;i<N-1;i++) ask.push_back(i);
    ask.push_back(pw);
    vi A= use_machine(ask);
    int xr = 0; 
    for (auto it: ask) if (!(it&pw))xr^=it;
    int has = 0,no = 0;
    for (auto it : A) {
      if (it&pw) has++;
      else no++;
    }
    for (auto it : A) {
      if ((it&pw) && has > no) xr^=it;
      else if ((!(it&pw)) && no > has) xr^=it;
    }
    vi ans(N);
    vi got(N,0);
    for (int i = 0;i<N;i++) {
      if ((A[i]^xr) < N-1) ans[i] = A[i]^xr,got[ans[i]] = 1;
    }
    int leftout=0;
    for (int i = 0;i<N;i++) if (!got[i]) leftout = i;
    for (int i = 0;i<N;i++){
      if ((A[i]^xr) < N-1) continue;
      ans[i] = leftout;
    }
    return ans;
  }
}

• 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: 0 / 31