| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 330564 | KWang31 | Longest beautiful sequence (IZhO17_subsequence) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 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<<8;
public static void main(String[] args){
FastReader br=new FastReader();
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();}
if(N<5000) {
int[] dp=new int[N]; Arrays.fill(dp, 1);
int[] child=new int[N];//Tracks the previous term of the sequence
Arrays.fill(child,-1);
for(int i=1;i<N;i++) {
for(int j=0;j<i;j++) {
if(Integer.bitCount(a[i]&a[j])==k[i]) {
if(1+dp[j]>dp[i]) {
dp[i]=dp[j]+1; child[i]=j;
}
}
}
}
int max=0; int ind=-1;
for(int i=0;i<N;i++) {
if(dp[i]>max) {
max=dp[i]; ind=i;
}
}
ArrayList<Integer> arl=new ArrayList<>();
while(ind >= 0) {
arl.add(ind);
ind=child[ind];
}
System.out.println(max);
StringBuilder sb=new StringBuilder();
for(int i=arl.size()-1; i>=0; i--) {
sb.append(arl.get(i)+1).append(" ");
}
System.out.println(sb.toString());
}else {
int[] dp=new int[MAX];
int[] map=new int[MAX]; Arrays.fill(map, -1);
int[] child=new int[N]; Arrays.fill(child,-1);
int mx;
for(int i=0;i<N;i++) {
mx=1;
for(int j=0;j<MAX;j++) {
if(Integer.bitCount(a[i]&j)!=k[i])continue;
if(dp[j]+1>mx) {
//System.out.println(i+" "+a[i]+" "+j);
mx=dp[j]+1; child[i]=map[j];//I may need to update child and map
}
}
dp[a[i]]=mx; map[a[i]]=i;
}
int ind=0; int max=0;
for(int i=0;i<MAX;i++) {
if(dp[i]>max) {
max=dp[i]; ind=map[i];
}
}
//System.out.println(Arrays.toString(dp));
//System.out.println(Arrays.toString(child));
ArrayList<Integer> arl=new ArrayList<>();
while(ind >= 0) {
arl.add(ind);
ind=child[ind];
}
System.out.println(max);
StringBuilder sb=new StringBuilder();
for(int i=arl.size()-1; i>=0; i--) {
sb.append(arl.get(i)+1).append(" ");
}
System.out.println(sb.toString());
}
}
//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!