#1167589 (C++23) No.3559 +A,-B

• 問題: No.3559 +A,-B
• ユーザー: iomir
• 提出日時: 2026-05-29 22:31:11
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 129 ms / 2,000 ms
• コード長: 3,621 bytes
• コンパイル時間: 2,470 ms
• コンパイル使用メモリ: 337,228 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-05-29 22:31:21
• 合計ジャッジ時間: 9,706 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

サブタスク	配点	結果
部分点1	10 %	AC * 4
部分点2	60 %	AC * 7
部分点3	30 %	AC * 20
合計	100 点

ソースコード

#include<bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

#define all(v) v.begin(),v.end()
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using vll=vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
using vp=vector<pair<ll, ll>>;
//using mint=modint1000000007;
//using mint=modint998244353;

const ll INF=1ll<<60;
ll mod10=1e9+7;
ll mod99=998244353;
const double PI = acos(-1);

#define rep(i,n) for (ll i=0;i<n;++i)
#define per(i,n) for(ll i=(n)-1;i>=0;--i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
#define per2(i,a,n) for (ll i=a;i>=n;--i)

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; }

bool solve(){
	ll N,x,y,a,b;cin>>N>>x>>y>>a>>b;

	ll sum=x+y;
	if(a<=0){
		if(sum<0){
			cout << x+a*N<<" "<<y << endl;
			return 0;
		}else{
			if(b<=0){
				cout << x<<" "<<y-N*b << endl;
				return 0;
			}else{
				ll c=sum/b+1;
				if(c>=N){
					cout << x<<" "<<y-N*b << endl;
					return 0;
				}
				N-=c;
				y-=b*c;
				sum=x+y;
				cout << x+a*N<<" "<<y << endl;
				return 0;
			}
		}
	}

	if(b<=0){
		if(sum<=0){
			ll c=(-sum)/a+((-sum)%a>0);
			if(c>=N){
				cout << x+a*N<<" "<<y << endl;
				return 0;
			}
			N-=c;
			x+=a*c;
			sum=x+y;
		}
		cout<<x<<" "<<y-b*N<<endl;
		return 0;
	}

	if(N<=-1){
		auto f=[&](ll& x,ll& y) -> void {
			if(x+y<0) x+=a;
			else y-=b;
		};
		rep(i,min(N,10ll)) f(x,y);
		cout << x<<" "<<y << endl;
		return 0;
	}


	ll l=-1,r=N;
	while(r-l>1){
		ll m=(l+r)/2;
		ll sum=x+a*m+(y-b*(N-m));
	//	cout << m<<" "<<x+a*m<<" "<<y-b*(N-m)<< " "<<sum << endl;
		
		if(sum>=-b) r=m;
		else l=m;
	}
	//cerr<<r<<" "<<N<< " "<<x<<" "<<y<<endl;
	cout << x+a*r<<" "<<y-b*(N-r) << endl;
	//cout  << endl;
	
	return 0;



	// a>0&&b>0
	
	if(sum<0){
		ll c=(-sum)/a;
		if(c>=N){
			cout << x+a*N<<" "<<y << endl;
			return 0;
		}
		N-=c;
		x+=a*c;
		sum=x+y;
		if(sum<0){
			x+=a;
			sum=x+y;
			N--;
		}
	}
	
	if(sum>=0){
		ll c=sum/b+1;
		if(c>=N){
			cout << x<<" "<<y-N*b << endl;
			return 0;
		}
		N-=c;
		y-=b*c;
		sum=x+y;
	}
	
		

	if(a==b){
		ll c1=(N+1)/2,c2=N/2;
		cout<<x+a*c1<<" "<<y-b*c2<<endl;
		return 0;
	}
	if(a>=b){
		if(a%b==0){
			ll k=a/b;
			ll c1=N/(k+1)+(N%(k+1));ll c2=N-c1;
			cout<<x+a*c1<<" "<<y-b*c2<<endl;
			return 0;
		}else{
			ll k=a%b;//増加
			ll c=(a-b)/b;//戻ってくるまで
			ll f=b/k*(c+1)+c+2;//1->c->1->c->1->c+1の合計

			
			if(N>=f){
				ll n=N/f;
				ll c1=(b/k+1)*n;ll c2=n*f-c1;
				x+=c1*a,y-=c2*b*n;
				N%=f;
			}
			
			ll c1=N/(1+c)+(N-N/(1+c)*(1+c)>0);
			ll c2=N-c1;
			cout<<x+c1*a<<" "<<y-c2*b<<endl;
			return 0;
		}
	}else{
		ll c=(-sum)/a;
		if(c>=N){
			cout << x+a*N<<" "<<y << endl;
			return 0;
		}
		N-=c;
		x+=a*c;
		sum=x+y;
		if(sum<0){
			x+=a;
			sum=x+y;
			N--;
		}
		cout << N<<" "<<x<<" "<<y << endl;
		
		
		if(b%a==0){
			ll k=b/a;
			ll c1=N/(k+1)+(N%(k+1));ll c2=N-c1;
			swap(c1,c2);
			cout<<x+a*c1<<" "<<y-b*c2<<endl;
			return 0;
		}else{
			ll k=b%a;//増加
			ll c=(-(a-1-b)+a-1)/a;//戻ってくるまで
			ll f=b/k*(c+1)+c+2;//1->c->1->c->1->c+1の合計

			
			if(N>=f){
				ll n=N/f;
				ll c1=(a+1)/k*n;ll c2=n*f-c1;
				swap(c1,c2);
				cout << c1+c2 << endl;
				
				x+=c1*a,y-=c2*b;
				N%=f;
			}
			ll c1=N/(1+c)+(N-N/(1+c)*(1+c)>0);
			ll c2=N-c1;
			cout << c1+c2 << endl;
			
			swap(c1,c2);
			cout<<x+c1*a<<" "<<y-c2*b<<endl;
			return 0;
		}

	}
	return 0;
}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll T=1;cin>>T;
	rep(i,T) solve();
}