結果
| 問題 | No.1017 Reiwa Sequence |
| ユーザー |
 Rubikun
|
| 提出日時 | 2020-04-03 23:19:43 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,136 bytes |
| コンパイル時間 | 2,090 ms |
| コンパイル使用メモリ | 187,812 KB |
| 実行使用メモリ | 29,968 KB |
| 最終ジャッジ日時 | 2023-09-16 04:50:58 |
| 合計ジャッジ時間 | 14,179 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
4,880 KB |
| testcase_01 | AC | 3 ms
4,820 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 4 ms
5,476 KB |
| testcase_04 | AC | 2 ms
4,376 KB |
| testcase_05 | AC | 3 ms
5,476 KB |
| testcase_06 | AC | 3 ms
5,404 KB |
| testcase_07 | AC | 2 ms
4,376 KB |
| testcase_08 | AC | 2 ms
4,376 KB |
| testcase_09 | AC | 13 ms
5,340 KB |
| testcase_10 | AC | 19 ms
7,788 KB |
| testcase_11 | AC | 7 ms
5,432 KB |
| testcase_12 | AC | 234 ms
29,968 KB |
| testcase_13 | AC | 61 ms
13,124 KB |
| testcase_14 | AC | 12 ms
4,952 KB |
| testcase_15 | AC | 31 ms
4,832 KB |
| testcase_16 | AC | 12 ms
4,812 KB |
| testcase_17 | AC | 277 ms
4,860 KB |
| testcase_18 | AC | 12 ms
4,908 KB |
| testcase_19 | AC | 48 ms
7,740 KB |
| testcase_20 | AC | 49 ms
7,728 KB |
| testcase_21 | AC | 46 ms
6,928 KB |
| testcase_22 | AC | 48 ms
7,548 KB |
| testcase_23 | AC | 44 ms
7,200 KB |
| testcase_24 | AC | 40 ms
6,868 KB |
| testcase_25 | AC | 43 ms
7,184 KB |
| testcase_26 | AC | 38 ms
6,664 KB |
| testcase_27 | AC | 34 ms
7,776 KB |
| testcase_28 | AC | 35 ms
7,812 KB |
| testcase_29 | AC | 18 ms
7,808 KB |
| testcase_30 | AC | 17 ms
6,980 KB |
| testcase_31 | AC | 20 ms
7,772 KB |
| testcase_32 | AC | 27 ms
7,200 KB |
| testcase_33 | AC | 14 ms
6,132 KB |
| testcase_34 | AC | 2 ms
4,376 KB |
| testcase_35 | AC | 3 ms
4,380 KB |
| testcase_36 | AC | 2 ms
4,376 KB |
| testcase_37 | AC | 30 ms
5,944 KB |
| testcase_38 | AC | 3 ms
5,024 KB |
| testcase_39 | WA | - |
| testcase_40 | AC | 25 ms
5,344 KB |
| testcase_41 | AC | 25 ms
5,804 KB |
| testcase_42 | AC | 23 ms
5,436 KB |
| testcase_43 | AC | 24 ms
5,368 KB |
| testcase_44 | AC | 21 ms
5,352 KB |
| testcase_45 | AC | 24 ms
5,348 KB |
| testcase_46 | AC | 23 ms
5,340 KB |
| testcase_47 | AC | 23 ms
5,340 KB |
| testcase_48 | AC | 27 ms
4,820 KB |
| testcase_49 | AC | 29 ms
6,124 KB |
| testcase_50 | AC | 26 ms
4,812 KB |
| testcase_51 | AC | 3 ms
4,812 KB |
| testcase_52 | AC | 35 ms
5,444 KB |
| testcase_53 | AC | 25 ms
7,476 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int N;cin>>N;
vector<int> A(N),cnt(150003),B;
for(int i=0;i<N;i++){
cin>>A[i];
cnt[A[i]]++;
}
B=A;
for(int i=0;i<150003;i++){
if(cnt[i]>=2){
cout<<"Yes"<<endl;
int a=0;
for(int j=0;j<N;j++){
if(A[j]==i){
if(a==0) a++;
else if(a==1){
A[j]*=-1;
a++;
}else A[j]=0;
}else A[j]=0;
}
for(int j=0;j<N;j++){
if(j) cout<<" ";
cout<<A[j];
}
cout<<endl;
return 0;
}
}
sort(all(A));
if(N>=1000){
vector<pair<int,int>> when(150003,{-1,-1});
for(int i=0;i+1<N;i++){
int a=when[A[i+1]-A[i]].first;
if(a!=-1&&a!=i-1){
int p1=A[when[A[i+1]-A[i]].first],p2=A[i+1];
int m1=A[when[A[i+1]-A[i]].second],m2=A[i];
for(int j=0;j<N;j++){
if(B[j]==p1||B[j]==p2) continue;
if(B[j]==m1||B[j]==m2) B[j]*=-1;
else B[j]=0;
}
cout<<"Yes"<<endl;
for(int j=0;j<N;j++){
if(j) cout<<" ";
cout<<B[j];
}
cout<<endl;
return 0;
}
if(a==-1){
when[A[i+1]-A[i]]={i,i+1};
}
}
}
vector<pair<int,int>> when(150003,{-1,-1});
for(int l=1;l<N;l++){
for(int i=0;i+l<N;i++){
int j=i+l;
int a=when[A[j]-A[i]].first,b=when[A[j]-A[i]].second;
if(i==a||i==b||j==a||j==b) continue;
if(a!=-1){
for(int k=0;k<N;k++){
if(B[k]==A[i]||B[k]==A[b]) continue;
if(B[k]==A[j]||B[k]==A[a]) B[k]*=-1;
else B[k]=0;
}
cout<<"Yes"<<endl;
for(int k=0;k<N;k++){
if(k) cout<<" ";
cout<<B[k];
}
cout<<endl;
return 0;
}
if(a==-1){
when[A[j]-A[i]]={i,j};
}
}
}
if(N<=18){
for(int bit=0;bit<(1<<N);bit++){
for(int U=bit;;U=(U-1)&bit){
int V=bit-U;
ll suma=0,sumb=0;
for(int i=0;i<N;i++){
if(U&(1<<i)) suma+=A[i];
if(V&(1<<i)) sumb+=A[i];
}
if(suma&&suma==sumb){
vector<int> use(150003);
for(int i=0;i<N;i++){
if(U&(1<<i)) use[A[i]]=1;
if(V&(1<<i)) use[A[i]]=2;
}
for(int i=0;i<N;i++){
if(use[B[i]]==0) B[i]=0;
else if(use[B[i]]==2) B[i]*=-1;
}
cout<<"Yes"<<endl;
for(int i=0;i<N;i++){
if(i) cout<<" ";
cout<<B[i];
}
cout<<endl;
return 0;
}
if(U==0) break;
}
}
cout<<"No"<<endl;
return 0;
}
A=B;
map<ll,pair<vector<int>,vector<int>>> MA;
for(int bit=0;bit<(1<<(N/2));bit++){
for(int U=bit;;U=(U-1)&bit){
int V=bit-U;
vector<int> a,b;
ll suma=0,sumb=0;
for(int i=0;i<N/2;i++){
if(U&(1<<i)){
suma+=A[i];
a.push_back(i);
}
if(V&(1<<i)){
sumb+=A[i];
b.push_back(i);
}
}
if(suma&&sumb){
MA[suma-sumb]={a,b};
if(suma==sumb){
for(int i=0;i<N;i++){
bool ok=false;
for(int j=0;j<a.size();j++){
if(i==a[j]) ok=true;
}
for(int j=0;j<b.size();j++){
if(i==b[j]){
A[i]*=-1;
ok=true;
}
}
if(!ok) A[i]=0;
}
cout<<"Yes"<<endl;
for(int i=0;i<N;i++){
if(i) cout<<" ";
cout<<A[i];
}
cout<<endl;
return 0;
}
}
if(U==0) break;
}
}
for(int bit=0;bit<(1<<(N-N/2));bit++){
for(int U=bit;;U=(U-1)&bit){
int V=bit-U;
vector<int> a,b;
ll suma=0,sumb=0;
for(int i=N/2;i<N;i++){
if(U&(1<<(i-N/2))){
suma+=A[i];
a.push_back(i);
}
if(V&(1<<(i-N/2))){
sumb+=A[i];
b.push_back(i);
}
}
if(suma&&sumb){
if(MA.count(sumb-suma)){
vector<int> c=MA[sumb-suma].first,d=MA[sumb-suma].second;
for(int x:c) a.push_back(x);
for(int x:d) b.push_back(x);
for(int i=0;i<N;i++){
bool ok=false;
for(int j=0;j<a.size();j++){
if(i==a[j]) ok=true;
}
for(int j=0;j<b.size();j++){
if(i==b[j]){
A[i]*=-1;
ok=true;
}
}
if(!ok) A[i]=0;
}
cout<<"Yes"<<endl;
for(int i=0;i<N;i++){
if(i) cout<<" ";
cout<<A[i];
}
cout<<endl;
return 0;
}
if(suma==sumb){
for(int i=0;i<N;i++){
bool ok=false;
for(int j=0;j<a.size();j++){
if(i==a[j]) ok=true;
}
for(int j=0;j<b.size();j++){
if(i==b[j]){
A[i]*=-1;
ok=true;
}
}
if(!ok) A[i]=0;
}
cout<<"Yes"<<endl;
for(int i=0;i<N;i++){
if(i) cout<<" ";
cout<<A[i];
}
cout<<endl;
return 0;
}
}
if(U==0) break;
}
}
cout<<"No"<<endl;
}