結果
| 問題 |
No.2287 ++ -- *=a /=a
|
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2023-04-28 23:22:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,129 bytes |
| コンパイル時間 | 2,512 ms |
| コンパイル使用メモリ | 226,456 KB |
| 最終ジャッジ日時 | 2025-02-12 15:39:38 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 16 TLE * 9 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long 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 all(x) (x).begin(),(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=1LL<<60;
map<vector<ll>,ll> MA;
ll A;
int le(vector<ll> S,vector<ll> T){
int au=0;
for(int i=0;i<min(si(S),si(T));i++){
if(S[i]!=T[i]) return au;
au++;
}
return au;
}
ll solve(vector<ll> SS,vector<ll> T){
priority_queue<pair<ll,vector<ll>>,vector<pair<ll,vector<ll>>>,greater<pair<ll,vector<ll>>>> PQ;
PQ.push(mp(0LL,SS));
MA[SS]=0LL;
ll res=INF;
while(!PQ.empty()){
auto [d,S]=PQ.top();PQ.pop();
if(d>=res) break;
if(MA[S]<d) continue;
if(S==T){
chmin(res,d);
continue;
}
if(si(S)==1&&S[0]==0){
chmin(res,d+si(T));
continue;
}
if(si(S)==0){
chmin(res,d+si(T));
continue;
}
int au=0;
for(int i=0;i<min(si(S),si(T));i++){
if(S[i]!=T[i]) break;
au++;
}
if(si(S)<si(T)){
if(au==si(S)){
chmin(res,d+si(T)-si(S));
continue;
}
}
ll x=S.back();
if(si(S)<=si(T)&&au==si(S)-1){
if(x<T[au]){
S.back()=T[au];
if(!MA.count(S)||chmin(MA[S],d+T[au]-x)){
MA[S]=d+T[au]-x;
PQ.push(mp(MA[S],S));
}
//chmin(res,T[au]-x+solve(S,T));
S.back()=x;
}else{
ll now=0;
for(ll a:S){
now*=A;
now+=a;
}
now+=(A+T[au]-x);
vector<ll> nx;
while(now){
nx.push_back(now%A);
now/=A;
}
reverse(all(nx));
if(1){
if(!MA.count(nx)||chmin(MA[nx],d+A+T[au]-x)){
MA[nx]=d+A+T[au]-x;
PQ.push(mp(MA[nx],nx));
}
}
//chmin(res,A+T[au]-x+solve(nx,T));
}
if(x>T[au]){
S.back()=T[au];
if(!MA.count(S)||chmin(MA[S],d+x-T[au])){
MA[S]=d+x-T[au];
PQ.push(mp(MA[S],S));
}
//chmin(res,x-T[au]+solve(S,T));
S.back()=x;
}else if(si(S)>=2){
ll now=0;
for(ll a:S){
now*=A;
now+=a;
}
now-=(x+A-T[au]);
vector<ll> nx;
while(now){
nx.push_back(now%A);
now/=A;
}
reverse(all(nx));
if(1){
if(!MA.count(nx)||chmin(MA[nx],d+A+x-T[au])){
MA[nx]=d+A+x-T[au];
PQ.push(mp(MA[nx],nx));
}
//chmin(res,(x+A-T[au])+solve(nx,T));
}
}
}
if(x==0){
ll now=0;
for(ll a:S){
now*=A;
now+=a;
}
now--;
vector<ll> nx;
while(now){
nx.push_back(now%A);
now/=A;
}
reverse(all(nx));
if(le(nx,T)==min(si(nx),si(T))){
if(!MA.count(nx)||chmin(MA[nx],d+1)){
MA[nx]=d+1;
PQ.push(mp(MA[nx],nx));
}
}
}
if(x==A-1){
ll now=0;
for(ll a:S){
now*=A;
now+=a;
}
now++;
vector<ll> nx;
while(now){
nx.push_back(now%A);
now/=A;
}
reverse(all(nx));
if(le(nx,T)==min(si(nx),si(T))){
if(!MA.count(nx)||chmin(MA[nx],d+1)){
MA[nx]=d+1;
PQ.push(mp(MA[nx],nx));
}
}
}
if(S.back()==0){
S.pop_back();
if(!MA.count(S)||chmin(MA[S],d+1)){
MA[S]=d+1;
PQ.push(mp(MA[S],S));
}
//chmin(res,1+solve(S,T));
S.push_back(x);
}
{
S.back()=0;
if(!MA.count(S)||chmin(MA[S],d+x)){
MA[S]=d+x;
PQ.push(mp(MA[S],S));
}
//chmin(res,x+solve(S,T));
S.back()=x;
}
{
ll now=0;
for(ll a:S){
now*=A;
now+=a;
}
now+=(A-x);
vector<ll> nx;
while(now){
nx.push_back(now%A);
now/=A;
}
reverse(all(nx));
if(!MA.count(nx)||chmin(MA[nx],d+A-x)){
MA[nx]=d+A-x;
PQ.push(mp(MA[nx],nx));
}
//chmin(res,A-x+solve(nx,T));
}
}
return res;
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int Q;cin>>Q;
while(Q--){
ll s,t;cin>>s>>t>>A;
MA.clear();
vector<ll> S,T;
while(s){
S.push_back(s%A);
s/=A;
}
while(t){
T.push_back(t%A);
t/=A;
}
reverse(all(S));
reverse(all(T));
cout<<solve(T,S)<<"\n";
}
}