結果

問題 No.539 インクリメント
ユーザー ei1333333
提出日時 2017-06-30 22:37:43
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 1,636 bytes
コンパイル時間 1,349 ms
コンパイル使用メモリ 166,588 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 20:35:17
合計ジャッジ時間 2,413 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
struct UnionFind
{
vector< int > data;
UnionFind(int sz)
{
data.assign(sz, -1);
}
bool unite(int x, int y)
{
x = find(x), y = find(y);
if(x == y) return (false);
if(data[x] > data[y]) swap(x, y);
data[x] += data[y];
data[y] = x;
return (true);
}
int find(int k)
{
if(data[k] < 0) return (k);
return (data[k] = find(data[k]));
}
int size(int k)
{
return (-data[find(k)]);
}
};
typedef long long int64;
void solve()
{
int T;
cin >> T;
cin.ignore();
while(T--) {
string S;
getline(cin, S);
UnionFind tree(S.size());
for(int i = 1; i < S.size(); i++) {
if(isdigit(S[i - 1]) && isdigit(S[i]))
tree.unite(i - 1, i);
}
string X, Y, Z;
int root = -1;
for(int i = S.size() - 1; i >= 0; i--) {
if(isdigit(S[i])) {
root = tree.find(i);
for(int j = i; j >= 0; j--) {
if(tree.find(j) == root) Z += S[j];
}
break;
}
X += S[i];
}
if(root == -1) {
cout << S << endl;
continue;
}
reverse(begin(X), end(X));
reverse(begin(Z), end(Z));
for(int i = 0; i < S.size(); i++) {
if(tree.find(i) == root) break;
Y += S[i];
}
bool inc = false;
for(int i = Z.size() - 1; i >= 0; i--) {
if(Z[i] == '9') {
inc = true;
Z[i] = '0';
} else {
inc = false;
Z[i]++;
break;
}
}
if(inc) Z = "1" + Z;
cout << Y << Z << X << endl;
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0