제출 #238007

#제출 시각아이디문제언어결과실행 시간메모리
238007DavidDamianDrvca (COCI19_drvca)C++11
50 / 110
10 ms1408 KiB
#include <bits/stdc++.h> using namespace std; ///Subtask 2 ///Dynamic Programming typedef pair<int,int> pii; map<pii,int> memo[305]; map<pii,int> dir[305]; int A[305]; int n; bool correct(int last,int diff,int x) { if(diff==-1) return true; if(x-A[last]!=diff) return false; return true; } int possible(int i,int last,int diff,int last2,int diff2) { if(i==n && last2!=-1) return 1; else if(i==n && last2==-1) return 0; pii state=make_pair(last,diff); if(memo[i].find(state)==memo[i].end()){ memo[i][state]=0; if(correct(last,diff,A[i])){ int newDiff=0; if(last==-1) newDiff=-1; else if(diff==-1) newDiff=A[i]-A[last]; else newDiff=diff; memo[i][state]=possible(i+1,i,newDiff,last2,diff2); dir[i][state]=0; } if(memo[i][state]==0){ if(correct(last2,diff2,A[i])){ int newDiff=0; if(last2==-1) newDiff=-1; else if(diff2==-1) newDiff=A[i]-A[last2]; else newDiff=diff2; memo[i][state]=possible(i+1,last,diff,i,newDiff); dir[i][state]=1; } } } return memo[i][state]; } vector<int> A1; vector<int> A2; void getSolution(int i,int last,int diff,int last2,int diff2) { if(i==n) return; pii state=make_pair(last,diff); if(dir[i][state]==0){ A1.push_back(A[i]); int newDiff=0; if(last==-1) newDiff=-1; else if(diff==-1) newDiff=A[i]-A[last]; else newDiff=diff; getSolution(i+1,i,newDiff,last2,diff2); } else{ A2.push_back(A[i]); int newDiff=0; if(last2==-1) newDiff=-1; else if(diff2==-1) newDiff=A[i]-A[last2]; else newDiff=diff2; getSolution(i+1,last,diff,i,newDiff); } } int main() { cin>>n; for(int i=0;i<n;i++){ cin>>A[i]; } sort(A,A+n); if(possible(0,-1,-1,-1,-1)){ getSolution(0,-1,-1,-1,-1); cout<<A1.size()<<'\n'; for(int x: A1){ cout<<x<<" "; } cout<<'\n'; cout<<A2.size()<<'\n'; for(int x: A2){ cout<<x<<" "; } cout<<'\n'; } else cout<<-1<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...