Submission #346705

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
346705	2021-01-10T18:43:54 Z	spatarel	Cup of Jamshid (IOI17_cup)	C++17	100 / 100	1 ms	364 KB

cup

#include "cup.h"
#include <stdio.h>

/*
x = 01011010
y = 11100010
------------- XOR
    10111000

x   = 0101101000
x-1 = 0101100111
------------------ XOR
      0000001111
      0000000001
------------------ +
      0000010000 / 2
lsbX= 0000001000
//*/

const int OFFSET = 500000002;

int ask(int x, int y) {
  return ask_shahrasb(x - OFFSET, y - OFFSET);
}

std::vector<int> get_result(int x, int y) {
  std::vector<int> result(2);
  result[0] = x - OFFSET;
  result[1] = y - OFFSET;
  return result;
}

std::vector<int> find_cup() {
  int xy = ask(0, 0);  // x XOR y
  int x1y = ask(1, 0); // (x - 1) XOR y
  int xx1 = xy ^ x1y;  // (x XOR y) XOR ((x - 1) XOR y) = (x XOR (x - 1)) XOR (y XOR y) = (x XOR (x - 1)) XOR 0 = x XOR (x - 1) = ?
  int x = (xx1 + 1) / 2;
  int initialXY = xy;
  //printf("x = %d", lsb);
  do {
    //xy = ask(x, 0);
    xy = initialXY ^ x;
    x1y = ask(x + 1, 0);
    xx1 = xy ^ x1y;
    x += (xx1 + 1) / 2;
    //printf(" + %d", (xx1 + 1) / 2);
  } while((xx1 + 1) / 2 > 1);
  x--;
  //printf("xy = %d\n", xy);
  //printf("x1y = %d\n", x1y);
  //printf(" = %d\n", lsb);
  int y = initialXY ^ x;
  //printf("x = %d ", x);
  //printf("y = %d\n", y);
  return get_result(x, y);
}

Subtask #1

100.0 / 100.0

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