이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7,sze = 1e5 +23,inf = INT_MAX, L = 18;
int check(vector<int> arr){
if(arr.empty()) return 0;
int n = arr.size();
for(int i=1;i+1<n;i++){
if((arr[i+1]-arr[i]) != arr[i]-arr[i-1]){
return 0;
}
}
return 1;
}
void print(vector<int> arr,vector<int> brr){
if(brr.empty()){
brr.pb(arr.back());arr.pop_back();
}
cout<<arr.size()<<"\n";
for(auto v:arr) cout<<v<<" "; cout<<endl;
cout<<brr.size()<<"\n";
for(auto v:brr) cout<<v<<" "; cout<<endl;
}
int equalz(vector<int> arr,int n,int eq){
vector<int> a,b;
for(auto v:arr){
if(v==eq){
a.pb(v);
}
else{
b.pb(v);
}
}
if(b.empty()){
b.pb(a.back());
a.pop_back();
}
if(check(b)){
print(a,b);
return 1;
}
if(a.size()>1){
b.pb(a.back());
a.pop_back();
sort(all(b));
}
if(check(b)){
print(a,b);
return 1;
}
return 0;
}
int lg[sze];
pair<int,int> dp[L][sze];
pair<int,int> qry(int l,int r){
if(r<l){
return {-1,-1};
}
int i = lg[r-l+1];
pair<int,int> res;
res.first = min(dp[i][l].first,dp[i][r - (1<<(i)) +1 ].first);
res.second = max(dp[i][l].second,dp[i][r - (1<<(i)) +1 ].second);
return res;
}
void opt1z(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
lg[i]=lg[i/2] +1;
}
vector<int> arr(n);
map<int,int> count;
int eq=-1;
for(int i=0;i<n;i++){
count[arr[i]]++;
cin>>arr[i];
if(eq!=-1 && count[arr[i]]>1){
eq=arr[i];
}
}
/*
eq:
x,x,x,x
a,a+k, x? , a+3k...
x,x,x
a,b,c,d
idx:
n-1,i,...j
f[i] : i sonuncu olsa, evvelki diff, => & 0 -> i-1 diff
*/
sort(all(arr));
if(eq!=-1){
if(equalz(arr,n,eq)){
return;
}
}
// for(auto v:arr) cout<<v<<" ";cout<<endl;
for(int i=0;i+1<n;i++){
dp[0][i].first=(arr[i+1]-arr[i]);
dp[0][i].second=(arr[i+1]-arr[i]);
// cout<<i<<" "<<arr[i+1]-arr[i]<<endl;
}
int m2=n-1;
for(int i =1;i<L;i++){
for(int j=0;j+ (1<<i)<=m2;j++){
dp[i][j].first = min(
dp[i-1][j].first,dp[i-1][j + (1<<(i-1))].first
);
dp[i][j].second = max(
dp[i-1][j].second,dp[i-1][j + (1<<(i-1))].second
);
}
}
map<int,int> last;
for(int i=0;i<n;i++){
last[arr[i]]=i;
}
map<int,int> mem;
mem[0]=1;
set<int> ff;
for(int im=0;im+1<n;im++){
int ferq = arr.back()-arr[im];
if(mem[ferq]){
continue;
}
mem[ferq]=1;
vector<int> lst;
lst.pb(n-1);
lst.pb(im);
int curr = arr[im];
while(true){
curr = curr-ferq;
if(!last.count(curr)){
break;
}
lst.pb(last[curr]);
}
// cout<<ferq<<": ";
// for(auto v:lst) cout<<v<<" ";cout<<endl;
int m = lst.size();
vector<pair<int,int>> f(m,{0,-1});
vector<int> f3(m,-1);
f[0].first=1;
f[0].second=-1;
int arxaferq = -1;
for(int i=1;i<m;i++){
if(!f[i-1].first){
break;
}
int rx = lst[i-1]-1;
int lx = lst[i]+1;
if(lx>rx){
f[i].first = 1;
f[i].second = f[i-1].second;
continue;
}
int lan2 = arr[lx];
pair<int,int> orta = qry(lx,rx-1);
if(orta.first!=orta.second){
break;
}
int connection=-1;
if(f[i-1].second != -1){
connection = f[i-1].second - arr[rx];
// cout<<connection<<endl;
}
ff.clear();
if(connection!=-1){
ff.ins(connection);
}
if(orta.first!=-1){
ff.ins(orta.first);
}
if(arxaferq!=-1){
ff.ins(arxaferq);
}
// cout<<i<<" => ";
// cout<<orta.first<<" "<<arxaferq<<" "<<connection<<" "<<endl;
// cout<<endl;
if(ff.size()>1){
break;
}
if(!ff.empty()){
// cout<<i<<" "<<"Sa"<<endl;
arxaferq = (*ff.begin());
}
f3[i]=arxaferq;
f[i].second = lan2;
f[i].first = 1;
}
// cout<<ferq<<" =: ";
// for(auto v:lst) cout<<arr[v]<<" ";cout<<endl;
// for(int i=0;i<m;i++){
// cout<<f[i].first<<" "<<f[i].second<<"\n";
// }
// cout<<endl;
for(int i =0;i<m;i++){
if(!f[i].first){
break;
}
int f2 = f3[i];
pair<int,int> zero = qry(0,lst[i]-2);
if(zero.first!=zero.second){
continue;
}
ff.clear();
int connection =-1;
if(lst[i]>0 && f[i].second!=-1 ){
connection = f[i].second - arr[lst[i]-1];
// cout<<ferq<<" "<<i<<" "<<connection<<" "<<f[i].second<<endl;
}
if(zero.first!=-1){
ff.ins(zero.first);
}
if(f2!=-1){
ff.ins(f2);
}
if(connection!=-1){
ff.ins(connection);
}
if(ff.size()<2){
map<int,int> used;
vector<int> a,b;
for(int j=0;j<=i;j++){
used[lst[j]]=1;
a.pb(arr[lst[j]]);
}
reverse(all(a));
for(int j=0;j<n;j++){
if(!used[j]){
b.pb(arr[j]);
}
}
print(a,b);
return;
}
}
}
putr(-1);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
// cin>>tt;
while(tt--){
opt1z();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
drvca.cpp: In function 'void print(std::vector<long long int>, std::vector<long long int>)':
drvca.cpp:26:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
26 | for(auto v:arr) cout<<v<<" "; cout<<endl;
| ^~~
drvca.cpp:26:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
26 | for(auto v:arr) cout<<v<<" "; cout<<endl;
| ^~~~
drvca.cpp:28:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
28 | for(auto v:brr) cout<<v<<" "; cout<<endl;
| ^~~
drvca.cpp:28:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
28 | for(auto v:brr) cout<<v<<" "; cout<<endl;
| ^~~~
# | 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... |