Submission #527395

#	Time	Username	Problem	Language	Result	Execution time	Memory
527395		rsjw	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2793 ms	93376 KiB

subsequence

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 100000
#define M (1<<20)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound 
using namespace std;
int n,m,k,Ns,C[N+5],Ch,La[N+5],Mx,x,y,K=(1<<10),dp[N+5],A[N+5],H[1025],B[N+5],F[M+5][11],Id[M+5][11];
int main(){
	//freopen("1.in","r",stdin);
	RI i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);for(i=1;i<K;i++) H[i]=H[i>>1]+(i&1);
	for(i=1;i<=n;i++){
		dp[i]=1;for(j=0;j<K;j++) x=((A[i]>>10)<<10)|j,y=B[i]-H[A[i]&j],y>=0&&y<=10&&dp[i]<F[x][y]+1&&(dp[i]=F[x][y]+1,La[i]=Id[x][y]);
		for(j=0;j<M;j+=K) x=j|(A[i]&(K-1)),y=H[(A[i]&j)>>10],F[x][y]<dp[i]&&(F[x][y]=dp[i],Id[x][y]=i);Mx=max(Mx,dp[i]);
	}for(i=1;i<=n;i++) if(dp[i]==Mx){Ns=i;break;}while(Ns) C[++Ch]=Ns,Ns=La[Ns];printf("%d\n",Ch);for(i=Ch;i;i--) printf("%d ",C[i]);
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:32:118: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |   dp[i]=1;for(j=0;j<K;j++) x=((A[i]>>10)<<10)|j,y=B[i]-H[A[i]&j],y>=0&&y<=10&&dp[i]<F[x][y]+1&&(dp[i]=F[x][y]+1,La[i]=Id[x][y]);
      |                                                                                                                 ~~~~~^~~~~~~~~
subsequence.cpp:33:94: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |   for(j=0;j<M;j+=K) x=j|(A[i]&(K-1)),y=H[(A[i]&j)>>10],F[x][y]<dp[i]&&(F[x][y]=dp[i],Id[x][y]=i);Mx=max(Mx,dp[i]);
      |                                                                                      ~~~~~~~~^~
subsequence.cpp:33:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   33 |   for(j=0;j<M;j+=K) x=j|(A[i]&(K-1)),y=H[(A[i]&j)>>10],F[x][y]<dp[i]&&(F[x][y]=dp[i],Id[x][y]=i);Mx=max(Mx,dp[i]);
      |   ^~~
subsequence.cpp:33:98: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   33 |   for(j=0;j<M;j+=K) x=j|(A[i]&(K-1)),y=H[(A[i]&j)>>10],F[x][y]<dp[i]&&(F[x][y]=dp[i],Id[x][y]=i);Mx=max(Mx,dp[i]);
      |                                                                                                  ^~
subsequence.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  RI i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);for(i=1;i<K;i++) H[i]=H[i>>1]+(i&1);
      |         ~~~~~^~~~~~~~~
subsequence.cpp:30:47: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  RI i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);for(i=1;i<K;i++) H[i]=H[i>>1]+(i&1);
      |                                          ~~~~~^~~~~~~~~~~~
subsequence.cpp:30:83: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  RI i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);for(i=1;i<K;i++) H[i]=H[i>>1]+(i&1);
      |                                                                              ~~~~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60