이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*; import java.util.*;
public class subsequence{
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());
}
}
static int MOD=998244353;
static int MAX=1<<10;
public static void main(String[] args){
FastReader br=new FastReader();
int[] btcnt=new int[MAX]; for(int i=0;i<MAX;i++) {btcnt[i]=Integer.bitCount(i);}
int[][][] M=new int[MAX][MAX][11]; for(int i=0;i<MAX;i++)for(int j=0;j<MAX;j++)Arrays.fill(M[i][j],-1);
int[][][] ind=new int[MAX][MAX][11];
int N=br.nextInt(); int[] a=new int[N]; int[] k=new int[N];
for(int i=0;i<N;i++) {a[i]=br.nextInt();}
for(int i=0;i<N;i++) {k[i]=br.nextInt();}
int q=0; int r=a[0]&(MAX-1); int z; int[] prev=new int[N];
Arrays.fill(prev, -1);
int[] ans=new int[N];
/*
ans[0]=1;
for(int j=0;j<MAX;j++) {
M[j][r][btcnt[j&r]]++; ind[j][r][btcnt[j&r]]=0;
}*/
for(int i=0;i<N;i++) {
q=a[i]>>>10; r=a[i]&(MAX-1);
ans[i]++;
for(int j=0;j<MAX;j++) {//QUERY
z=k[i]-btcnt[r&j];
if(z>=0 && z<=10 ) { //The first 10 bits have EXACTLY z bits in common
if( M[q][j][z]+1>ans[i]) {
ans[i]=M[q][j][z]+1; prev[i]=ind[q][j][z];
}
}
}
//UPDATE
for(int j=0;j<MAX;j++) {
if(M[j][r][btcnt[j&q]]<ans[i]) {
M[j][r][btcnt[j&q]]=ans[i]; ind[j][r][btcnt[j&q]]=i;
}
}
}
int mx=0; int cur=-1;
for(int i=0;i<N;i++) {
if(ans[i]>mx) {
mx=ans[i]; cur=i;
}
}
//System.out.println(Arrays.toString(ans));
System.out.println(mx);
ArrayList<Integer> arl=new ArrayList<>();
arl.add(cur+1);
while(cur>0) {
cur=prev[cur]; arl.add(cur+1);
}
for(int i=mx-1;i>=0;i--) {
System.out.print(arl.get(i)+" ");
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |