답안 #22829 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22829	2017-04-30T07:45:54 Z	- - - - - - - List of honorable mention follows - - - - - - -(#999, xhae, ainu7, littlesheep)	Joyful KMP (KRIII5_JK)	C++11	7 / 7	419 ms	240552 KB

#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <cctype>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <queue>
#include <stdint.h>
#include <stdio.h>
#include <stack>
#include <ctime>
#include <list>
#include <map>
#include <set>
#include <tuple>
#include <unordered_set>
#include <assert.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define TR(i,x) for(__typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALL(x) x.begin(),x.end()
#define SORT(x) sort(ALL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))

using namespace std;

#define PB push_back
#define MP make_pair

typedef map<int,int> MII;
typedef map<string,int> MSI;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<long double> VD;
typedef pair<int,int> PII;
typedef long long int64;
typedef long long LL;
typedef unsigned int UI;
typedef long double LD;
typedef unsigned long long ULL;

const int N = 1000007;
const int MOD = 1000000007;

char s[N];
char answer[N];

int n;
VI same[N];
VI diff[N];
VI nodes[N];
int diffCount[N];

int kmp[N];
int color[N];

int clusterDiffCount[N];
VI clusterDiff[N];

void dfs(int x, int c) {
    color[x] = c;
    nodes[c].PB(x);
    if (diffCount[x] != 0) {
        assert(!clusterDiffCount[c]);
        clusterDiffCount[c] = diffCount[x];
        clusterDiff[c] = diff[x];
    }
    TR(it, same[x]) {
        if (color[*it] == -1) {
            dfs(*it, c);
        }
    }
}

bool used[N];

int main() {
    scanf("%s", s);
    n = strlen(s);
    LL k;
    cin >> k;

    kmp[0] = -1;
    for (int i = 1; i < n; ++i) {
        int current = kmp[i - 1];
        while (current != -1 && s[current + 1] != s[i]) {
            current = kmp[current];
        }
        if (s[current + 1] == s[i]) {
            ++current;
        }
        kmp[i] = current;
    }

    for (int i = 1; i < n; ++i) {
        if (kmp[i] != -1) {
            same[i].PB(kmp[i]);
            same[kmp[i]].PB(i);
            // cout << "SAME " << i << ", " << kmp[i] << endl;
            continue;
        } else {
            ++diffCount[i];
            diff[i].PB(0);
        }
        diffCount[i] = 1;
        int current = kmp[i - 1];
        while (current != -1 && s[current + 1] != s[i]) {
            if (kmp[current + 1] == -1) {
                ++diffCount[i];
                diff[i].PB(current + 1);
                // cout << "DIFF " << i << ", " << current + 1 << endl;
            }
            current = kmp[current];
        }
    }

    FILL(color, -1);
    int colors = 0;
    for (int i = 0; i < n; ++i) {
        if (color[i] == -1) {
            dfs(i, colors++);
        }
    }

    VI clusterRep;
    REP(i, n) {
        if (!used[color[i]]) {
            clusterRep.PB(i);
            used[color[i]] = true;
        }
    }

    assert(clusterRep.size() == colors);
    vector<LD> doubleWays(colors + 1);
    vector<LL> ways(colors + 1);
    vector<LL> modWays(colors + 1);
    doubleWays[colors] = 1;
    ways[colors] = modWays[colors] = 1;
    for (int i = colors - 1; i >= 0; --i) {
        int at = clusterRep[i];
        assert(26 - clusterDiffCount[color[at]] > 0);
        doubleWays[i] = 26 - clusterDiffCount[color[at]];
        ways[i] = 26 - clusterDiffCount[color[at]];
        modWays[i] = 26 - clusterDiffCount[color[at]];
        if (i != colors - 1) {
            doubleWays[i] = min((LD) 1e30, doubleWays[i] * doubleWays[i + 1]);
            ways[i] *= ways[i + 1];
            modWays[i] = modWays[i] * modWays[i + 1] % MOD;
        }
    }

    LD bound = 9.1e18;
    cout << modWays[0] << endl;
    if (doubleWays[0] < bound && k > ways[0]) {
        cout << "OVER" << endl;
        return 0;
    }
    for (int i = 0; i < colors; ++i) {
        int at = clusterRep[i];
        bool found = false;
        for (char c = 'a'; c <= 'z'; ++c) {
            bool ban = false;
            TR(it, clusterDiff[color[at]]) {
                assert(answer[*it]);
                if (c == answer[*it]) {
                    ban = true;
                    break;
                }
            }
            if (ban) continue;
            if (doubleWays[i + 1] < bound) {
                if (k > ways[i + 1]) {
                    k -= ways[i + 1];
                    continue;
                }
            }
            found = true;
            TR(it, nodes[color[at]]) {
                answer[*it] = c;
            }
            break;
        }
        assert(found);
    }
    printf("%s\n", answer);
    return 0;
}

Compilation message

In file included from JK.cpp:27:0:
JK.cpp: In function 'int main()':
JK.cpp:143:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(clusterRep.size() == colors);
                              ^
JK.cpp:88:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
                   ^

Subtask #1
7.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	114328 KB	Output is correct
2	Correct	23 ms	114328 KB	Output is correct
3	Correct	23 ms	114328 KB	Output is correct
4	Correct	23 ms	114460 KB	Output is correct
5	Correct	269 ms	240280 KB	Output is correct
6	Correct	243 ms	240540 KB	Output is correct
7	Correct	243 ms	240320 KB	Output is correct
8	Correct	256 ms	240552 KB	Output is correct
9	Correct	243 ms	240284 KB	Output is correct
10	Correct	26 ms	114328 KB	Output is correct
11	Correct	26 ms	114328 KB	Output is correct
12	Correct	19 ms	114460 KB	Output is correct
13	Correct	33 ms	114728 KB	Output is correct
14	Correct	26 ms	115120 KB	Output is correct
15	Correct	26 ms	118360 KB	Output is correct
16	Correct	29 ms	121956 KB	Output is correct
17	Correct	139 ms	153420 KB	Output is correct
18	Correct	239 ms	193100 KB	Output is correct
19	Correct	249 ms	191900 KB	Output is correct
20	Correct	233 ms	190984 KB	Output is correct
21	Correct	243 ms	193196 KB	Output is correct
22	Correct	246 ms	191744 KB	Output is correct
23	Correct	353 ms	151420 KB	Output is correct
24	Correct	366 ms	154412 KB	Output is correct
25	Correct	366 ms	153484 KB	Output is correct
26	Correct	419 ms	151396 KB	Output is correct
27	Correct	379 ms	152088 KB	Output is correct
28	Correct	349 ms	151648 KB	Output is correct
29	Correct	399 ms	152088 KB	Output is correct
30	Correct	339 ms	153392 KB	Output is correct
31	Correct	313 ms	153828 KB	Output is correct
32	Correct	343 ms	154056 KB	Output is correct
33	Correct	346 ms	151644 KB	Output is correct
34	Correct	326 ms	153048 KB	Output is correct
35	Correct	333 ms	151648 KB	Output is correct
36	Correct	333 ms	153760 KB	Output is correct
37	Correct	326 ms	152880 KB	Output is correct
38	Correct	346 ms	151656 KB	Output is correct
39	Correct	363 ms	151968 KB	Output is correct
40	Correct	336 ms	151592 KB	Output is correct
41	Correct	349 ms	151932 KB	Output is correct
42	Correct	413 ms	152960 KB	Output is correct
43	Correct	303 ms	152736 KB	Output is correct
44	Correct	129 ms	196508 KB	Output is correct
45	Correct	146 ms	196508 KB	Output is correct
46	Correct	289 ms	155336 KB	Output is correct
47	Correct	276 ms	155336 KB	Output is correct
48	Correct	296 ms	153508 KB	Output is correct
49	Correct	293 ms	153508 KB	Output is correct
50	Correct	293 ms	153508 KB	Output is correct

답안 #22829

Compilation message

Subtask #1 7.0 / 1.0

Subtask #1
7.0 / 1.0