| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 343964 | KWang31 | Longest beautiful sequence (IZhO17_subsequence) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <iostream>
#define pb push_back
using namespace std;
const int MAX = 1 << 10;
const int MAXN=100001;
int a[MAXN]; int k[MAXN]; int prev[MAXN]; int ans[MAXN];
int main(){
int btcnt[MAX]; for(int i=0;i<MAX;i++){btcnt[i]=__builtin_popcount(i);}
int N;
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<N;i++){
scanf("%d",&k[i]);
}
int M[MAX][MAX][11];
int ind[MAX][MAX][11];
for(int i=0;i<MAX;i++)
for(int j=0;j<MAX;j++)
for(int k=0;k<11; k++)
M[i][j][k]=-1;
int q,z; int r=a[0]&(MAX-1);
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;
}
}
printf("%d\n", mx);
vector<int> seq;
seq.pb(cur+1);
while(cur>0){
cur=prev[cur]; seq.pb(cur+1);
}
for (int i=mx-1; i>=0; i--){
printf("%d ", seq[i]);
}
return 0;
}