이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
long long res=1;
while (b>0){
if (b%2==1) res=(res*a)%p;
b/=2;
a=(a*a)%p;
}
return res;
}
int n,arr[100001],brr[100001];
// idea 1: dp1[x] = LBS ending with x
// idea 2: dp2[i][k] = max length of LBS ending with x
// over all x such that bitcount(x&i)=k
// for idea 2, we get O(1) transitions
// but we then need to update O(M) states in dp2
// idea 1 has O(M) transition, O(1) affected states
// idea 2 has O(1) transition, O(M) affected states
int dp[1100][1100][11],from[1100][1100][11],prv[100001];
// main idea is to split X into its left and right bits
// lx is left bits, rx is right bits
// dp[i][j][k] = max legnth of LBS ending with x such that
// lx = i
// bitcount(rx&j) = k
// from just stores the last index of the LBS
void runtc(){
cin>>n;
for (int i=1;i<=n;i++){
cin>>arr[i];
}
for (int i=1;i<=n;i++){
cin>>brr[i];
}
pair<int,int> ans=mp(1,-1);
memset(prv,-1,sizeof(prv));
for (int id=1;id<=n;id++){
int lx=arr[id]>>10;
int rx=arr[id]%(1<<10);
int lbs=1; //answer for id
for (int i=0;i<(1<<10);i++){
int rbits=brr[id]-__builtin_popcount(lx&i);
if (rbits<0 | rbits>10) continue;
if (dp[i][rx][rbits]+1>lbs){
lbs=dp[i][rx][rbits]+1;
prv[id]=from[i][rx][rbits];
}
}
cout<<id<<' '<<lbs<<'\n';
ans=max(ans,mp(lbs,id));
for (int j=0;j<(1<<10);j++){
int rbits=__builtin_popcount(rx&j);
if (lbs>dp[lx][j][rbits]){
dp[lx][j][rbits]=lbs;
from[lx][j][rbits]=id;
}
}
}
vector<int> res;
while (ans.second!=-1){
res.pb(ans.second);
ans.second=prv[ans.second];
}
reverse(res.begin(),res.end());
cout<<res.size()<<'\n';
for (auto i:res){
cout<<i<<' ';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("movie.in","r",stdin);
// freopen("movie.out","w",stdout);
// freopen("input1.in","r",stdin);
// freopen("output1.out","w",stdout);
//freopen("tower_rush_input.txt","r",stdin);
//freopen("hackercup_output.txt","w",stdout);
int tcs;
// cin>>tcs;
tcs=1;
for (int i=1;i<=tcs;i++){
// cout<<"Case #"<<i<<": ";
runtc();
}
}
컴파일 시 표준 에러 (stderr) 메시지
subsequence.cpp: In function 'void runtc()':
subsequence.cpp:52:22: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
52 | if (rbits<0 | rbits>10) continue;
| ~~~~~^~
# | 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... |