結果
問題 | No.539 インクリメント |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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();}