/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* class ArrayReader {
* public:
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* int query(int a, int b, int c, int d);
*
* // Returns the length of the array
* int length();
* };
*/
class Solution {
public:
int guessMajority(ArrayReader &reader) {
}
};
# """
# This is the ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader(object):
# # Compares 4 different elements in the array
# # return 4 if the values of the 4 elements are the same (0 or 1).
# # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
# # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
# def query(self, a: int, b: int, c: int, d: int) -> int:
#
# # Returns the length of the array
# def length(self) -> int:
#
class Solution:
def guessMajority(self, reader: 'ArrayReader') -> int:
length = reader.length()
equalTo0 = [0]
unequalTo0 = []
case1 = reader.query(0, 1, 2, 3)
case2 = reader.query(1, 2, 3, 4)
case3 = reader.query(0, 2, 3, 4)
case4 = reader.query(0, 1, 3, 4)
case5 = reader.query(0, 1, 2, 4)
if case2 == case3:
# i0 == i1
equalTo0.append(1)
else:
# i0 != i1
unequalTo0.append(1)
if case2 == case4:
# i0 == i2
equalTo0.append(2)
else:
# !0 != i2
unequalTo0.append(2)
if case2 == case5:
# i0 == i3
equalTo0.append(3)
else:
# !0 != i3
unequalTo0.append(3)
for i in range(4, length):
case = reader.query(1, 2, 3, i)
if case1 == case:
equalTo0.append(i)
else:
unequalTo0.append(i)
# print(equalTo0)
# print(unequalTo0)
if len(equalTo0) == len(unequalTo0):
return -1
elif len(equalTo0) > len(unequalTo0):
return equalTo0[0]
else:
return unequalTo0[0]
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* struct ArrayReader;
* impl ArrayReader {
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* pub fn query(a: i32, b: i32, c: i32, d: i32) -> i32 {}
*
* // Returns the length of the array
* pub fn length() -> i32 {}
* };
*/
impl Solution {
pub fn get_majority(reader: &ArrayReader) -> i32 {
let n = reader.length() as usize;
let mut z = 1;
let mut o = 0;
for i in 1..n {
let mut other = vec![];
for j in 1..n {
if j != i {
other.push(j);
}
if other.len() == 3 {
break;
}
}
let mut q1 = vec![0];
let mut q2 = vec![i as i32];
for j in other {
q1.push(j as i32);
q2.push(j as i32);
}
q2.sort();
if reader.query(q1[0], q1[1], q1[2], q1[3]) != reader.query(q2[0], q2[1], q2[2], q2[3]) {
o += 1;
} else {
z += 1;
}
if o > n / 2 || z > n / 2 {
return i as i32;
}
}
-1
}
}
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* interface ArrayReader {
* public:
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* public int query(int a, int b, int c, int d);
*
* // Returns the length of the array
* public int length();
* };
*/
class Solution {
public int guessMajority(ArrayReader reader) {
int n=reader.length();
int start=reader.query(0,1,2,3);
int i1=3;int i2=-1;
int group1=1,group2=0;
//假设 index3 是group1
for(int i=4;i<n;i++){
int q=reader.query(0,1,2,i);
if(q==start)group1++;
else {
i2=i;
group2++;
}
}
//再看前面3个值
int sudo=reader.query(0,1,2,4);
//test 0
if(reader.query(1,2,3,4)==sudo){
group1++;
}else{
group2++;
i2=0;
}
//test 2
if(reader.query(0,1,3,4)==sudo){
group1++;
}else{
group2++;i2=2;
}
//test1
if(reader.query(0,2,3,4)==sudo){
group1++;
}else{
group2++;i2=1;
}
if(group1==group2)return -1;
if(group1>group2)return i1;
return i2;
}
}
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* class ArrayReader {
* public:
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* int query(int a, int b, int c, int d);
*
* // Returns the length of the array
* int length();
* };
*/
class Solution {
public:
int guessMajority(ArrayReader &reader) {
int n = reader.length();
vector<int> v(n);
v[0] = 1;
auto find = [&](int num) {
int idx = -1;
for (int i = 0; i < n; ++i) {
if (v[i] == num) {
idx = i;
break;
}
}
return idx;
};
int q0123 = reader.query(0, 1, 2, 3);
int q0124 = reader.query(0, 1, 2, 4);
int q0134 = reader.query(0, 1, 3, 4);
int q0234 = reader.query(0, 2, 3, 4);
int q1234 = reader.query(1, 2, 3, 4);
v[1] = (q0234 == q1234);
v[2] = (q0134 == q1234);
v[3] = (q0124 == q1234);
v[4] = (q0123 == q1234);
int prev = q1234;
for (int i = 5; i < n; ++i) {
int curr = reader.query(i - 3, i - 2, i - 1, i);
v[i] = (prev == curr ? v[i - 4] : 1 - v[i - 4]);
prev = curr;
}
int sum = accumulate(v.begin(), v.end(), 0);
if (sum * 2 == n) {
return -1;
}
return sum * 2 < n ? find(0) : find(1);
}
};
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* class ArrayReader {
* public:
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* int query(int a, int b, int c, int d);
*
* // Returns the length of the array
* int length();
* };
*/
class Solution {
public:
int guessMajority(ArrayReader &reader) {
int n = reader.length();
vector<int> v(n);
v[0] = 1;
auto checkIfSame = [&](int p, int q) {
vector<int> chooseP = {p};
vector<int> chooseQ = {q};
for (int i = 0; i < n; ++i) {
if (i != p && i != q) {
chooseP.push_back(i);
chooseQ.push_back(i);
if (chooseP.size() == 4) {
break;
}
}
}
sort(chooseP.begin(), chooseP.end());
sort(chooseQ.begin(), chooseQ.end());
return reader.query(chooseP[0], chooseP[1], chooseP[2], chooseP[3]) == \
reader.query(chooseQ[0], chooseQ[1], chooseQ[2], chooseQ[3]);
};
auto find = [&](int num) {
int idx = -1;
for (int i = 0; i < n; ++i) {
if (v[i] == num) {
idx = i;
break;
}
}
return idx;
};
for (int i = 1; i < n; ++i) {
v[i] = checkIfSame(0, i);
}
int sum = accumulate(v.begin(), v.end(), 0);
if (sum * 2 == n) {
return -1;
}
return sum * 2 < n ? find(0) : find(1);
}
};