Submission #542973

#	Time	Username	Problem	Language	Result	Execution time	Memory
542973		Olympia	Domino (COCI15_domino)	C++17	0 / 160	3191 ms	359808 KiB

domino

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>

using namespace std;
class Graph {
public:
    vector<int> weight;
    vector<vector<int>> adj;
    vector<bool> dp;
    void add_edge (int u, int v) {
        adj[u][v] = adj[v][u] = 1;
    }
    Graph (int n, vector<int> weight) {
        adj.resize(n), dp.resize((1 << n));
        for (int i = 0; i < n; i++) {
            adj[i].resize(n);
        }
        this->weight = weight;
    }
    void read () {
        int n = adj.size();
        for (int i = 1; i < (1 << n); i++) {
            if (__builtin_popcount(i) == 1) {
                dp[i] = true;
                continue;
            }
            bool fine = true;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    if (!adj[log2(i)][j]) {
                        fine = false;
                    }
                }
            }
            dp[i] = fine;
        }
    }
};

class Edges {
public:
    pair<int,int> from;
    pair<int,int> to;
    int weight;
    bool operator < (const Edges& e1) const {
        if (e1.weight != weight) return (weight > e1.weight);
        return make_pair(from, to) < make_pair(e1.from, e1.to);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K; cin >> N >> K;
    vector<vector<int>> grid(N);
    for (int i = 0; i < N; i++) {
        grid[i].resize(N);
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
        }
    }
    vector<Edges> vec;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (abs(dx) + abs(dy) != 1) {
                        continue;
                    }
                    if (i + dx < 0 || i + dx == N || j + dy < 0 || j + dy == N) {
                        continue;
                    }
                    vec.push_back({make_pair(i + dx, j + dy), make_pair(i, j), grid[i + dx][j + dy] + grid[i][j]});
                }
            }
        }
    }
    sort(vec.begin(), vec.end());
    int cntr = 0;
    vector<Edges> m;
    set<pair<int,int>> edges1, edges2;
    for (auto& e: vec) {
        cntr++;
        if (cntr == 100) {
            break;
        }
        if (cntr % 2 == 0) {
            m.push_back(e);
        }
    }
    for (int i = 0; i < 20; i++) {
        edges1.insert(m[i].from), edges1.insert(m[i].to);
    }
    for (int i = 20; i < 50; i++) {
        edges2.insert(m[i].from), edges2.insert(m[i].to);
    }
    map<pair<int,int>,int> m1, m2;
    cntr = 0;
    for (auto& p: edges1) {
        m1[p] = cntr++;
    }
    for (auto& p: edges2) {
        m2[p] = cntr++;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10