結果
問題 | No.2745 String Swap Battle |
ユーザー | 0214sh7 |
提出日時 | 2024-04-21 05:44:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 2,618 bytes |
コンパイル時間 | 2,407 ms |
コンパイル使用メモリ | 204,464 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-04-21 05:44:30 |
合計ジャッジ時間 | 3,877 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
5,248 KB |
testcase_01 | AC | 10 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 13 ms
5,376 KB |
testcase_07 | AC | 14 ms
5,376 KB |
testcase_08 | AC | 14 ms
5,376 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 7 ms
5,376 KB |
testcase_11 | AC | 5 ms
5,376 KB |
testcase_12 | AC | 163 ms
9,472 KB |
testcase_13 | AC | 157 ms
9,472 KB |
testcase_14 | AC | 162 ms
9,600 KB |
testcase_15 | AC | 15 ms
5,376 KB |
testcase_16 | AC | 15 ms
5,376 KB |
testcase_17 | AC | 15 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> PP; // #define MOD 1000000007 #define MOD 998244353 #define INF 2305843009213693951 //#define INF 810114514 #define PI 3.141592653589 #define setdouble setprecision #define REP(i,n) for(ll i=0;i<(n);++i) #define OREP(i,n) for(ll i=1;i<=(n);++i) #define RREP(i,n) for(ll i=(n)-1;i>=0;--i) #define ORREP(i,n) for(ll i=(n);i>=1;--i) #define rep(i,a,b) for(ll i=(a);i<=(b);++i) #define ALL(v) (v).begin(), (v).end() #define GOODBYE do { cout << "-1" << endl; return 0; } while (false) #define MM <<" "<< #define Endl endl #define debug true #define debug2 false string change(string s){ vector<ll> B(26,0);REP(j,s.size()){B[s[j]-'a']++;} auto ss = s;sort(ALL(ss)); if(ss==s){ REP(j,26){ if(B[j]>=2){ return s; } } swap(s[s.size()-1],s[s.size()-2]); return s; } ll now = 0; while(B[now]==0)now++; REP(j,s.size()){ if(s[j]!='a'+now){ RREP(k,s.size()){ if(s[k]=='a'+now){ swap(s[j],s[k]); break; } } break; } B[now]--;while(B[now]==0)now++; } return s; } // string greedy(string s){ // ll N = s.size(); // string R = "zzzzzzzzzzzzzzzzzz"; // REP(i,N){ // rep(j,i+1,N-1){ // string t = s; // swap(t[i],t[j]); // R = min(R,t); // } // } // return R; // } int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); // REP(i,26){ // REP(j,26){ // REP(k,26){ // string s; // s.push_back('a'+i); // s.push_back('a'+j); // s.push_back('a'+k); // if(change(s)!=greedy(s)){ // cout << "! " << s MM change(s) MM greedy(s) << endl; // } // } // } // } ll N; cin >> N; vector<string> S(N); REP(i,N){ cin >> S[i]; } auto T = S; REP(i,N){ T[i] = change(S[i]); } // REP(i,N){ // cout << T[i] << endl; // } string m = T[0]; REP(j,N){ m = min(m,T[j]); } ll num = 0; REP(j,N){ if(T[j]==m)num++; } REP(j,N){ if(T[j]==m){ cout << N+1-num << endl; }else{ cout << 0 << endl; } } return 0; }