oj.uz

Submission #914185

# Submission time Handle Problem Language Result Execution time Memory
914185 2024-01-21T10:34:07 Z PieArmy Kpart (eJOI21_kpart) C++17
100 / 100
 1765 ms 2176 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    int main(){
        ios_base::sync_with_stdio(false);cin.tie(NULL);
        int t;cin>>t;
        while(t--){
            int n;cin>>n;
            int arr[n];
            int pref[n+1];pref[0]=0;
            for(int i=0;i<n;i++){cin>>arr[i];pref[i+1]=pref[i]+arr[i];}
            vector<int>dp(100001,-1);
            dp[0]=0;
            vector<int>nex(n+1,-1);
            vector<int>prev(0);
            int mx=0;
            for(int i=0;i<n;i++){
                prev.resize(pref[i+1]+2,-1);
                prev[pref[i+1]+1]=mx;
                int l=prev.back(),r=pref[i+1]+1;
                while(l!=-1){
                    while(prev[r]>=l+arr[i]){
                        r=prev[r];
                    }
                    if(l+arr[i]<=(pref[n]>>1)){
                        if(r==l+arr[i]){
                            dp[l+arr[i]]=max(dp[l+arr[i]],dp[l]);
                        }
                        else{
                            prev[l+arr[i]]=prev[r];
                            prev[r]=l+arr[i];
                            dp[l+arr[i]]=dp[l];
                        }
                    }
                    l=prev[l];
                }
                mx=prev[pref[i+1]+1];
                prev[pref[i+1]+1]=-1;
                dp[arr[i]]=i;
                int las=0,pos=nex[0];
                while(pos!=-1){
                    int sum=pref[i+1]-pref[i+1-pos];
                    if((sum&1)||dp[sum>>1]<=i-pos)nex[las]=nex[pos];
                    else las=pos;
                    pos=nex[pos];
                }
                if((pref[i+1]&1)==0&&dp[pref[i+1]>>1]!=-1)nex[las]=i+1;
            }
            vector<int>ans;
            int pos=nex[0];
            while(pos!=-1){
                ans.push_back(pos);
                pos=nex[pos];
            }
            cout<<ans.size()<<" ";
            for(int x:ans)cout<<x<<" ";
            cout<<"\n";
        }
        return 0;
    }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 25 ms 996 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 1136 KB Output is correct
2 Correct 264 ms 1284 KB Output is correct
3 Correct 305 ms 1344 KB Output is correct
4 Correct 563 ms 1492 KB Output is correct
5 Correct 1310 ms 2168 KB Output is correct
6 Correct 1765 ms 1920 KB Output is correct
7 Correct 1662 ms 2176 KB Output is correct