Submission #1031323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031323		PieArmy	Exam (eJOI20_exam)	C++17	100 / 100	106 ms	98752 KiB

exam

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

void code(){
    int n;cin>>n;
    int A[n],B[n];
    for(int i=0;i<n;i++)
        cin>>A[i];
    for(int i=0;i<n;i++)
        cin>>B[i];
    int us[n+1];
    int nex=2,bin=0;
    for(int i=1;i<=n;i++){
        us[i]=bin;
        if(nex==i){
            bin++;nex<<=1;
        }
    }
    int spar[us[n]+1][n];
    for(int i=0;i<n;i++){
        spar[0][i]=A[i];
    }
    for(int i=1;i<=us[n];i++){
        for(int j=0;j<=n-pie(i);j++){
            spar[i][j]=max(spar[i-1][j],spar[i-1][j+pie(i-1)]);
        }
    }
    if(n>5000){
        bool b=true;
        for(int i=1;i<n;i++)
            if(B[i]!=B[i-1]){
                b=false;break;
            }
        if(b){
            bool dp[n+1];for(bool &x:dp)x=false;
            bool cur=false;
            for(int i=0;i<n;i++){
                if(A[i]==B[0])cur=true;
                if(A[i]>B[0])cur=false;
                dp[i]|=cur;
            }
            cur=false;
            for(int i=n-1;i>=0;i--){
                if(A[i]==B[0])cur=true;
                if(A[i]>B[0])cur=false;
                dp[i]|=cur;
            }
            int ans=0;
            for(int i=0;i<n;i++)
                if(dp[i])
                    ans++;
            cout<<ans;
            return;
        }
        else{
            map<int,int>mp;
            for(int i=1;i<=n;i++)
                mp[A[i-1]]=i;
            vector<int>v;
            for(int i=0;i<n;i++){
                int j=mp[B[i]];
                if(j){
                    j--;
                    int boy=abs(i-j)+1;
                    int mx=max(spar[us[boy]][min(i,j)],spar[us[boy]][max(i,j)-pie(us[boy])+1]);
                    if(mx<=B[i])
                        v.pb(j+1);
                }
            }
            vector<int>ans;
            for(int x:v){
                int l=0,r=ans.size();
                while(l<r){
                    int m=(l+r)/2;
                    if(ans[m]<=x)l=m+1;
                    else r=m;
                }
                if(l==ans.size())ans.pb(x);
                else ans[l]=x;
            }
            cout<<ans.size();
            return;
        }
    }
    int dp[n+1][n+1];
    for(auto &x:dp)
        for(auto &y:x)
            y=-1;
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dp[i][j]==-1)continue;
            if(A[j]==B[i]){
                int boy=abs(i-j)+1;
                int mx=max(spar[us[boy]][min(i,j)],spar[us[boy]][max(i,j)-pie(us[boy])+1]);
                if(mx<=B[i]){
                    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+1);
                    continue;
                }
            }
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
        }
        if(dp[i][n]!=-1)
            dp[i+1][n]=max(dp[i+1][n],dp[i][n]);
    }
    for(int i=0;i<n;i++)
        if(dp[n][i]!=-1)
            dp[n][i+1]=max(dp[n][i+1],dp[n][i]);
    cout<<dp[n][n];
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    int t=1;
    if(!t)cin>>t;
    while(t--){code();cout<<endl;}
    return 0;
}

Compilation message (stderr)

exam.cpp: In function 'void code()':
exam.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                 if(l==ans.size())ans.pb(x);
      |                    ~^~~~~~~~~~~~
exam.cpp: In function 'int main()':
exam.cpp:125:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
exam.cpp:125:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22