Mujin Programming Challenge 2017

Submission #1303492

Source codeソースコード

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

typedef long long ll;
string S;
int Q;

vector<vector<int> > cc;
int dp(int l, int a) {
    if(l == S.size()) return 1e9;
    int &ret = cc[l][a];
    if(ret != -1) return ret;

    if(S[l] - 'a' == a) return ret = l + 1;
    if(S[l] - 'a' < a) {
        if(dp(l, a - 1) == 1e9) return ret = 1e9;
        else return ret = dp(dp(l, a - 1), a - 1);
    }
    else {
        if(dp(l, 26) == 1e9) return ret = 1e9;
        else return ret = dp(dp(l, 26), a);
    }
}
vector<vector<int> > db;

int main() {
    std::ios::sync_with_stdio(false);
    cin>>S>>Q;

    cc = vector<vector<int> >(S.size(), vector<int>(27, -1));
    db = vector<vector<int> >(S.size(), vector<int>(20, 1e9));
    for(int i = S.size() - 1; i >= 0; i--) {
        db[i][0] = dp(i, 26);
        for(int j = 1; j < 20; j++) {
            int t = db[i][j - 1];
            if(t == S.size() || t == 1e9) break;
            db[i][j] = db[t][j - 1];
        }
    }
    while(Q--) {
        int l, r; cin>>l>>r;
        l--;

        int p = l;
        for(int i = 20; i--;) {
            if(p != S.size() && db[p][i] <= r) {
                p = db[p][i];
            }
        }
        if(p == r) printf("Yes\n");
        else printf("No\n");
    }
}

Submission

Task問題 C - Robot and String
User nameユーザ名 choikiwon
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1300
Source lengthソースコード長 1317 Byte
File nameファイル名
Exec time実行時間 496 ms
Memory usageメモリ使用量 139804 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_00.txt,0_01.txt,0_02.txt
All 1300 / 1300 0_00.txt,0_01.txt,0_02.txt,1_00.txt,1_01.txt,1_02.txt,1_03.txt,1_04.txt,1_05.txt,1_06.txt,1_07.txt,1_08.txt,1_09.txt,1_10.txt,1_11.txt,1_12.txt,1_13.txt,1_14.txt,1_15.txt,1_16.txt,1_17.txt,1_18.txt,1_19.txt,1_20.txt,1_21.txt,1_22.txt,1_23.txt,1_24.txt,1_25.txt,1_26.txt,1_27.txt,1_28.txt,1_29.txt,1_30.txt,1_31.txt,1_32.txt,1_33.txt,1_34.txt,1_35.txt,1_36.txt,1_37.txt,1_38.txt,1_39.txt,1_40.txt,1_41.txt,1_42.txt,1_43.txt,1_44.txt,1_45.txt,1_46.txt,1_47.txt,1_48.txt,1_49.txt,1_50.txt,1_51.txt,1_52.txt,1_53.txt,1_54.txt,1_55.txt,1_56.txt,1_57.txt,1_58.txt,1_59.txt,1_60.txt,1_61.txt,1_62.txt,1_63.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
1_00.txt AC 23 ms 512 KB
1_01.txt AC 24 ms 512 KB
1_02.txt AC 404 ms 133916 KB
1_03.txt AC 352 ms 133916 KB
1_04.txt AC 347 ms 133916 KB
1_05.txt AC 339 ms 133916 KB
1_06.txt AC 369 ms 133916 KB
1_07.txt AC 364 ms 133916 KB
1_08.txt AC 197 ms 133916 KB
1_09.txt AC 195 ms 133916 KB
1_10.txt AC 191 ms 133916 KB
1_11.txt AC 189 ms 133916 KB
1_12.txt AC 191 ms 133916 KB
1_13.txt AC 200 ms 134044 KB
1_14.txt AC 194 ms 133916 KB
1_15.txt AC 198 ms 133916 KB
1_16.txt AC 192 ms 133916 KB
1_17.txt AC 206 ms 133916 KB
1_18.txt AC 205 ms 133916 KB
1_19.txt AC 213 ms 133916 KB
1_20.txt AC 211 ms 133916 KB
1_21.txt AC 220 ms 133916 KB
1_22.txt AC 239 ms 133916 KB
1_23.txt AC 245 ms 133916 KB
1_24.txt AC 276 ms 133916 KB
1_25.txt AC 311 ms 133916 KB
1_26.txt AC 336 ms 133916 KB
1_27.txt AC 354 ms 133916 KB
1_28.txt AC 392 ms 134044 KB
1_29.txt AC 385 ms 134044 KB
1_30.txt AC 355 ms 134044 KB
1_31.txt AC 334 ms 134044 KB
1_32.txt AC 318 ms 133916 KB
1_33.txt AC 193 ms 133916 KB
1_34.txt AC 170 ms 130332 KB
1_35.txt AC 180 ms 132636 KB
1_36.txt AC 180 ms 128540 KB
1_37.txt AC 195 ms 132124 KB
1_38.txt AC 195 ms 133788 KB
1_39.txt AC 206 ms 133916 KB
1_40.txt AC 211 ms 132636 KB
1_41.txt AC 228 ms 134044 KB
1_42.txt AC 224 ms 131612 KB
1_43.txt AC 245 ms 134044 KB
1_44.txt AC 254 ms 133916 KB
1_45.txt AC 257 ms 133660 KB
1_46.txt AC 263 ms 134428 KB
1_47.txt AC 271 ms 133020 KB
1_48.txt AC 313 ms 136476 KB
1_49.txt AC 348 ms 133916 KB
1_50.txt AC 496 ms 139804 KB
1_51.txt AC 292 ms 133916 KB
1_52.txt AC 412 ms 136860 KB
1_53.txt AC 288 ms 133916 KB
1_54.txt AC 432 ms 139804 KB
1_55.txt AC 264 ms 133916 KB
1_56.txt AC 343 ms 136860 KB
1_57.txt AC 256 ms 135708 KB
1_58.txt AC 250 ms 133916 KB
1_59.txt AC 319 ms 134044 KB
1_60.txt AC 261 ms 133916 KB
1_61.txt AC 249 ms 136860 KB
1_62.txt AC 195 ms 133916 KB
1_63.txt AC 249 ms 133916 KB