| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 336986 | KWang31 | Xoractive (IZhO19_xoractive) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*; import java.util.*;
public class Xoractive{
/*
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
}
public static class Pair implements Comparable<Pair>{
int vtx; int val;
public Pair(int a, int b){
this.vtx=a; this.val=b;
}
public int compareTo(Pair other){
if(this.val<other.val)return -1;
if(this.val>other.val)return 1;
if(this.vtx<other.vtx)return -1;
return 1;
}
}
static int MOD=998244353;
static int[] rk, p,siz;
public static void main(String[] args){
FastReader br=new FastReader();
int N=br.nextInt(); int M=br.nextInt();
//StringBuilder sb=new StringBuilder();
//System.out.println(sb.toString());
}
*/
public static int[] guess(int n) {
int[] ans=new int[n];
ans[0]=grader.ask(1);//Array is 1-indexed
ArrayList<Integer> S[][]=new ArrayList[7][2];
ArrayList<Integer> cur=new ArrayList<>();
ArrayList<Integer> all=new ArrayList<>();
for(int i=0;i<7;i++) {//Compute S[i][0]
S[i][0]=new ArrayList<>(); cur=new ArrayList<>();
for(int j=1;j<n;j++) {
if((j&(1<<i))==0) {
cur.add(j+1);//1-indexed!!
}
}
int[] x=grader.get_pairwise_xor(cur);
cur.add(1); int[] y=grader.get_pairwise_xor(cur);
int pter=0;while(x[pter]==0) {pter++;}//Ignore zero elements
int cnt=0; int jj;
for(int j=0; j<y.length; j++) {
if(y[j]==0)continue;
jj=j;
while(x[pter]==y[j] && y[j]==y[jj]) {
pter++; jj++;
}
if(x[pter]>y[j] && y[jj]==y[j]) {
S[i][0].add(y[j]);
}
j=jj;
//Compare
//x=[1,1,2,2,2]
//y=[1,1,2,2,3]
}
for(int j: S[i][0]) {
j^=ans[0];
if(!all.contains(j)) {
all.add(j);
}
}
}
for(int i=0;i<7;i++) {
S[i][1]=new ArrayList<>();
for(int j: all) {
if(!S[i][0].contains(j)) {
S[i][1].add(j);
}
}
}
for(int i=1; i<n;i++) {
for(int j: S[0][i&1]) {
boolean ok=true;
for(int k=1; k<7; k++) {
if(!S[k][(i>>>k)&1].contains(j)) {
ok=false; break;
}
}
if(ok) {
ans[i]=j; break;
}
}
}
return ans;
}
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!