oj.uz

Submission #1104487

# Submission time Handle Problem Language Result Execution time Memory
1104487 2024-10-23T23:26:43 Z aaaaaarroz Machine (IOI24_machine) C++17
100 / 100
 126 ms 708 KB 
#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

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 / 0.0

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 42 ms 336 KB Output is correct
3 Correct 27 ms 452 KB Output is correct
4 Correct 44 ms 452 KB Output is correct
5 Correct 67 ms 708 KB Output is correct
6 Correct 103 ms 584 KB Output is correct
7 Correct 126 ms 444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 44 ms 452 KB Output is correct
3 Correct 28 ms 460 KB Output is correct
4 Correct 58 ms 452 KB Output is correct
5 Correct 64 ms 708 KB Output is correct
6 Correct 106 ms 444 KB Output is correct
7 Correct 106 ms 448 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 44 ms 448 KB Output is correct
3 Correct 33 ms 336 KB Output is correct
4 Correct 48 ms 460 KB Output is correct
5 Correct 60 ms 592 KB Output is correct
6 Correct 105 ms 440 KB Output is correct
7 Correct 103 ms 336 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 35 ms 592 KB Output is correct
3 Correct 32 ms 336 KB Output is correct
4 Correct 60 ms 592 KB Output is correct
5 Correct 62 ms 452 KB Output is correct
6 Correct 109 ms 444 KB Output is correct
7 Correct 105 ms 444 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 33 ms 456 KB Output is correct
3 Correct 29 ms 460 KB Output is correct
4 Correct 52 ms 456 KB Output is correct
5 Correct 70 ms 336 KB Output is correct
6 Correct 107 ms 336 KB Output is correct
7 Correct 93 ms 440 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 46 ms 336 KB Output is correct
3 Correct 30 ms 464 KB Output is correct
4 Correct 51 ms 460 KB Output is correct
5 Correct 67 ms 504 KB Output is correct
6 Correct 109 ms 336 KB Output is correct
7 Correct 117 ms 336 KB Output is correct