結果
| 問題 |
No.3162 Five Two Three
|
| ユーザー |
 Rubikun
|
| 提出日時 | 2025-05-23 20:27:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,147 bytes |
| コンパイル時間 | 2,340 ms |
| コンパイル使用メモリ | 212,296 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-23 20:27:53 |
| 合計ジャッジ時間 | 18,728 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 177 WA * 10 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef __int128_t ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005;
const ll INF=15LL<<55;
//int128
//https://kopricky.github.io/code/Misc/int128.html
// __int128の入出力
using LL = __int128;
istream& operator>>(istream& is, LL& v)
{
string s;
is >> s;
v = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
}
if (s[0] == '-') { v *= -1; }
return is;
}
ostream& operator<<(ostream& os, const LL& v)
{
if (v == 0) { return (os << "0"); }
LL num = v;
if (v < 0) {
os << '-';
num = -num;
}
string s;
for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
reverse(s.begin(), s.end());
return (os << s);
}
LL abss(LL x){
return max(x,-x);
}
void check4(vl S){
for(int i=1;i<=2;i++){
if(abss(S[i-1]-S[i+1])!=S[i]) return;
}
cout<<4<<endl;
for(ll x:S) cout<<x<<" ";
cout<<endl;
exit(0);
}
ll dpa[MAX],dpb[MAX];
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
dpa[1]=1;
dpa[2]=1;
dpb[1]=1;
dpb[2]=2;
for(int i=3;i<=90;i++){
dpa[i]=dpa[i-1]+dpa[i-2];
dpb[i]=dpb[i-1]+dpb[i-2];
//cout<<i<<" "<<dpa[i]<<" "<<dpb[i]<<endl;
}
ll X,Y,Z;cin>>X>>Y>>Z;
if(abss(X-Y)==Z){
cout<<3<<endl;
cout<<X<<" "<<Z<<" "<<Y<<endl;
return 0;
}
check4({X,Z,abss(X+Z),Y});
check4({X,Z,abss(X-Z),Y});
check4({X,abss(Y+Z),Z,Y});
check4({X,abss(Y-Z),Z,Y});
vl ans(300);
for(int q=0;q<2;q++){
for(ll pos=1;pos<=90;pos++){
for(ll alen=pos+1;alen<=90;alen++){
for(ll blen=1;blen<=90;blen++){
if(pos==1&&blen==1) continue;
//if(alen==2) continue;
ll x=dpa[pos],y=dpb[pos];
ll u=dpa[alen],v=dpb[alen];
LL di=(LL)(Z)*u-(LL)(X)*x;
LL ke=(LL)(y)*u-(LL)(v)*x;
if(ke==0) continue;
if(ke<0){
di*=-1;
ke*=-1;
}
if(di%ke) continue;
LL b=di/ke;
LL a=((LL)(Z)-y*b)/x;
if(a*x!=Z-y*b) continue;
ll U=a+b;
vl S;
for(int i=2;i<=alen;i++) S.pb(a*dpa[i]+b*dpb[i]);
reverse(all(S));
if(blen>1){
x=dpa[1];y=dpb[1];
u=dpa[blen];v=dpb[blen];
di=(LL)(U)*u-(LL)(Y)*x;
ke=(LL)(y)*u-(LL)(v)*x;
if(ke==0) continue;
if(ke<0){
di*=-1;
ke*=-1;
}
if(di%ke) continue;
b=di/ke;
a=((LL)(U)-y*b)/x;
if(a*x!=U-y*b) continue;
for(int i=1;i<=blen;i++) S.pb(a*dpa[i]+b*dpb[i]);
}else{
S.pb(Y);
}
if(q) reverse(all(S));
bool ok=true;
for(int i=1;i<si(S)-1;i++){
ok&=(abss(S[i-1]-S[i+1])==S[i]);
}
for(int i=0;i<si(S);i++){
ok&=S[i]>=0;
}
if(!ok) continue;
if(si(ans)>si(S)){
ans=S;
}
}
}
}
swap(X,Y);
}
for(int q=0;q<2;q++){
for(ll K=5;K<=100;K++){
if(X){
ll L=0,R=X;
while(R-L>1){
ll M=(L+R)/2;
vl S={X,M,X-M,X};
for(int t=4;t<K;t++){
ll ne=S[t-1]+S[t-2];
chmin(ne,INF);
S.pb(ne);
}
if(S.back()>=Y) L=M;
else R=M;
}
ll M=L;
vl S={X,M,X-M,X};
for(int t=4;t<K;t++){
ll ne=S[t-1]+S[t-2];
chmin(ne,INF);
S.pb(ne);
}
bool a=false,b=false;
for(int i=1;i<si(S)-1;i++){
if(S[i]==Z) a=true;
}
if(S.back()==Y) b=true;
if(a&&b){
if(q) reverse(all(S));
if(si(ans)>si(S)){
ans=S;
}
}
}
{
ll L=-1,R=Y+1;
while(R-L>1){
ll M=(L+R)/2;
vl S={X,M};
for(int t=2;t<K;t++){
ll ne=S[t-1]+S[t-2];
chmin(ne,INF);
S.pb(ne);
}
if(S.back()>=Y) R=M;
else L=M;
}
//cout<<K<<" "<<R<<endl;
ll M=R;
vl S={X,M};
for(int t=2;t<K;t++){
ll ne=S[t-1]+S[t-2];
chmin(ne,INF);
S.pb(ne);
}
bool a=false,b=false;
for(int i=1;i<si(S)-1;i++){
if(S[i]==Z) a=true;
}
if(S.back()==Y) b=true;
if(a&&b){
if(q) reverse(all(S));
if(si(ans)>si(S)){
ans=S;
}
}
}
}
swap(X,Y);
}
if(si(ans)!=300){
cout<<si(ans)<<"\n";
for(ll x:ans) cout<<x<<" ";
cout<<"\n";
}else{
cout<<-1<<"\n";
}
}