Submission #1104487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104487		aaaaaarroz	Machine (IOI24_machine)	C++17	100 / 100	126 ms	708 KiB

machine

#include "machine.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>use_machine(vector<int> A);
vector<int> find_permutation(int N) {
  /*if(N==2){
    vector<int> A1 = {0, 1};
    vector<int> A2 = {1, 0};
    vector<int> B1 = use_machine(A1);
    vector<int> B2 = use_machine(A2);
    int X1 = B1[0] ^ A1[0];
    int X2 = B2[0] ^ A2[0];
    int X = (X1 == X2) ? X1 : (B1[1] ^ A1[1]);
    vector<int> P(2);
    if ((B1[0] ^ X) == A1[0] && (B1[1] ^ X) == A1[1]) {
      P = {0, 1};
    } 
    else {
      P = {1, 0};
    }
    return P;
  }
  else */if(N%2==0){
    map<int,int>pos;
    vector<int> A(N);
    A[0]=0;
    pos[0]=0;
    A[1]=1;
    pos[1]=1;
    for(int i=2;i<N-1;i++){
        A[i]=i+1;
        pos[i+1]=i;
    }
    A[N-1]=N+2;
    pos[N+2]=N-1;
    vector<int>P(N);
    vector<int>B=use_machine(A);
    int x;
    for(x=0;x<=255;x++){
      set<int>numeros;
      for(int numero:B){
        numeros.insert(numero^x);
      }
      auto itr=numeros.lower_bound(N-1);
      if(numeros.size()==N&&*numeros.begin()==0&&*next(next(numeros.begin()))==3&&*numeros.rbegin()==(N+2)&&N-1==*itr){
        break;
      }
    }
    for(int i=0;i<N;i++){
        P[i]=pos[B[i]^x];
    }
    return P;
  }
  else{
    map<int,int>pos;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        A[i]=i;
        pos[i]=i;
    }
    vector<int>P(N);
    vector<int>B=use_machine(A);
    int x;
    for(x=0;x<=255;x++){
      set<int>numeros;
      for(int numero:B){
        numeros.insert(numero^x);
      }
      if(numeros.size()==N&&*numeros.begin()==0&&*numeros.rbegin()==(N-1)){
        break;
      }
    }
    for(int i=0;i<N;i++){
        P[i]=pos[B[i]^x];
    }
    return P;
  }
}

Compilation message (stderr)

machine.cpp: In function 'std::vector<int> find_permutation(int)':
machine.cpp:45:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |       if(numeros.size()==N&&*numeros.begin()==0&&*next(next(numeros.begin()))==3&&*numeros.rbegin()==(N+2)&&N-1==*itr){
      |          ~~~~~~~~~~~~~~^~~
machine.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |       if(numeros.size()==N&&*numeros.begin()==0&&*numeros.rbegin()==(N-1)){
      |          ~~~~~~~~~~~~~~^~~

• 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