Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2018 Alkani C++ 100/100OK 13. okt '18 @ 14:33

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,992 MiB 0,046 s OK
#2 5/5 5,441 MiB 0,051 s OK
#3 5/5 5,445 MiB 0,044 s OK
#4 5/5 5,348 MiB 0,051 s OK
#5 5/5 5,355 MiB 0,045 s OK
#6 5/5 3,988 MiB 0,015 s OK
#7 5/5 5,441 MiB 0,051 s OK
#8 5/5 5,441 MiB 0,039 s OK
#9 5/5 5,445 MiB 0,051 s OK
#10 5/5 5,445 MiB 0,038 s OK
#11 5/5 5,355 MiB 0,033 s OK
#12 5/5 5,352 MiB 0,051 s OK
#13 5/5 5,445 MiB 0,039 s OK
#14 5/5 5,445 MiB 0,044 s OK
#15 5/5 3,207 MiB 0,004 s OK
#16 5/5 3,273 MiB 0,004 s OK
#17 5/5 3,180 MiB 0,004 s OK
#18 5/5 3,293 MiB 0,010 s OK
#19 5/5 3,188 MiB 0,000 s OK
#20 5/5 3,188 MiB 0,000 s OK

Ocenjevani program (alkani.cpp):
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

struct tuple3 {
    int x;
    int y;
    int z;
};

typedef std::pair<int, int> tuple2;

static int N = 0, M = 0;
static std::vector<std::string> image;
static std::vector<std::vector<int>> visited;
static std::vector<std::vector<int>> maxdir;
static std::map<std::string, int> results;

static const std::string names[13] = {
    "",
    "met",
    "et",
    "prop",
    "but",
    "pent",
    "heks",
    "hept",
    "okt",
    "non",
    "dek",
    "undek",
    "dodek"
};

static const std::string prefixes[13] = {
    "",
    "",
    "di",
    "tri",
    "tetra",
    "penta",
    "heksa",
    "hepta",
    "okta",
    "nona",
    "deka",
    "undeka",
    "dodeka"
};

static int ch_at(int x, int y) {
    if (x < 0 || x >= M || y < 0 || y >= N) return 0;
    return image[y][x];
}

static tuple3 find_longest(int x, int y, int v) {
    if (visited[y][x] >= v) return {0,0,0};
    visited[y][x] = v;
    if (ch_at(x, y) != 'C') return {0,0,0};
    tuple3 ret = {x,y,0};
    if (ch_at(x + 1, y) == '-') {
        tuple3 tmp = find_longest(x + 2, y, v);
        if (tmp.z > ret.z) {
            ret = tmp;
            if (v == 2) maxdir[y][x] = 1;
        }
    }
    if (ch_at(x - 1, y) == '-') {
        tuple3 tmp = find_longest(x - 2, y, v);
        if (tmp.z > ret.z) {
            ret = tmp;
            if (v == 2) maxdir[y][x] = 2;
        }
    }
    if (ch_at(x, y + 1) == '|') {
        tuple3 tmp = find_longest(x, y + 2, v);
        if (tmp.z > ret.z) {
            ret = tmp;
            if (v == 2) maxdir[y][x] = 4;
        }
    }
    if (ch_at(x, y - 1) == '|') {
        tuple3 tmp = find_longest(x, y - 2, v);
        if (tmp.z > ret.z) {
            ret = tmp;
            if (v == 2) maxdir[y][x] = 8;
        }
    }
    ret.z++;
    return ret;
}

static void find_chains(int x, int y, int nx, int ny, std::vector<tuple2>& outp, int i) {
    if (visited[y][x] >= 10) return;
    visited[y][x] = 10;
    if (ch_at(x, y) != 'C') return;
    if (x == nx && y == ny) return;
    if (ch_at(x + 1, y) == '-') {
        if (maxdir[y][x] == 1) find_chains(x + 2, y, nx, ny, outp, i + 1);
        else {
            tuple3 tmp = find_longest(x + 2, y, 10);
            if (tmp.z) outp.push_back(std::make_pair(i,tmp.z));
        }
    }
    if (ch_at(x - 1, y) == '-') {
        if (maxdir[y][x] == 2) find_chains(x - 2, y, nx, ny, outp, i + 1);
        else {
            tuple3 tmp = find_longest(x - 2, y, 10);
            if (tmp.z) outp.push_back(std::make_pair(i,tmp.z));
        }
    }
    if (ch_at(x, y + 1) == '|') {
        if (maxdir[y][x] == 4) find_chains(x, y + 2, nx, ny, outp, i + 1);
        else {
            tuple3 tmp = find_longest(x, y + 2, 10);
            if (tmp.z) outp.push_back(std::make_pair(i,tmp.z));
        }
    }
    if (ch_at(x, y - 1) == '|') {
        if (maxdir[y][x] == 8) find_chains(x, y - 2, nx, ny, outp, i + 1);
        else {
            tuple3 tmp = find_longest(x, y - 2, 10);
            if (tmp.z) outp.push_back(std::make_pair(i,tmp.z));
        }
    }
}

static bool find_smaller_chain(std::vector<tuple2>& la, std::vector<tuple2>& lb) {
    for (int i = 0, n = la.size(); i < n; i++) {
        if (la[i].first < lb[i].first) return false;
        if (la[i].first > lb[i].first) return true;
    }
    for (int i = 0, n = la.size(); i < n; i++) {
        if (names[la[i].second] < names[lb[i].second]) return false;
        if (names[la[i].second] > names[lb[i].second]) return true;
    }
    return false;
}

static std::string recurse(int x, int y) {
    tuple3 maxlen = find_longest(x, y, 1);
    if (!maxlen.z) return "";
    tuple3 maxlen2 = find_longest(maxlen.x, maxlen.y, 2);
    int clen = maxlen2.z;
    std::vector<tuple2> chains1;
    find_chains(maxlen.x, maxlen.y, maxlen2.x, maxlen2.y, chains1, 1);
    std::sort(chains1.begin(), chains1.end());
    std::vector<tuple2> chains2 = chains1;
    std::reverse(chains2.begin(), chains2.end());
    for (auto it = chains2.begin(), end = chains2.end(); it != end; it++) {
        it->first = clen - it->first + 1;
    }
    std::vector<tuple2>& schain = (find_smaller_chain(chains1, chains2) ? chains2 : chains1);
    std::map<std::string, std::multiset<int>> sorted;
    for (auto it = schain.begin(), end = schain.end(); it != end; it++) {
        std::string key = names[it->second] + "il";
        sorted[key].insert(it->first);
    }
    std::string str = "";
    for (auto it = sorted.begin(), end = sorted.end(); it != end; it++) {
        std::multiset<int>& nums = it->second;
        std::string numss = "";
        for (auto it2 = nums.begin(), end2 = nums.end(); it2 != end2; it2++) {
            if (numss.size()) numss += ",";
            numss += std::to_string(*it2);
        }
        str += numss + "-" + prefixes[nums.size()] + it->first + "-";
    }
    str += names[clen] + "an";
    return str;
}

int main() {
    std::cin >> N;
    std::cin >> M;
    image.resize(N);
    visited.resize(N);
    maxdir.resize(N);
    for (int i = 0; i < N; i++) {
        std::cin >> image[i];
        visited[i].resize(M);
        maxdir[i].resize(M);
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            std::string ret = recurse(j, i);
            if (ret.size()) results[ret]++;
        }
    }
    std::set<std::pair<int, std::string>> outp;
    for (auto it = results.begin(), end = results.end(); it != end; it++) {
        outp.insert(std::make_pair(-it->second, it->first));
    }
    for (auto it = outp.begin(), end = outp.end(); it != end; it++) {
        std::cout << (-it->first) << "x " << it->second << std::endl;
    }
    return 0;
}