Submission #542996

#	Time	Username	Problem	Language	Result	Execution time	Memory
542996		Olympia	Domino (COCI15_domino)	C++17	0 / 160	3360 ms	524288 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<pair<int,int>> dp;
    void print () {
        for (int i = 0; i < adj.size(); i++) {
            for (int j = 0; j < adj.size(); j++) {
                cout << adj[i][j];
            }
            cout << '\n';
        }
        cout << '\n';
    }
    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++) {
            dp[i].first = weight[i];
            dp[i].second = 1;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    if (!adj[log2(i)][j]) {
                        
                    }
                }
            }
        }
    }
};

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);
    }
    bool intersects (const Edges& e2) const {
        return (e2.from == from || e2.from == to || e2.to == from || e2.to == to);
    }
};

Graph compress (vector<Edges> v, vector<vector<int>> grid) {
    vector<int> weights(v.size());
    for (int i = 0; i < v.size(); i++) {
        weights[i] = v[i].weight;
    }
    Graph gr (v.size(), weights);
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v.size(); j++) {
            if (!v[i].intersects(v[j])) {
                gr.add_edge(i, j);
            }
        }
    }
    return gr;
}

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());
    vector<Edges> m;
    set<pair<int,int>> edges1, edges2;
    for (int i = 0; i < vec.size(); i++) {
        if (i == 100) {
            break;
        }
        if (i % 2 == 0) {
            m.push_back(vec[i]);
        }
    }
    vector<Edges> m1, m2;
    for (int i = 0; i < m.size(); i++) {
        if (i < 20) m1.push_back(m[i]);
        else m2.push_back(m[i]);
    }
    Graph g = compress(m, grid);
    Graph g1 = compress(m1, grid);
    Graph g2 = compress(m2, grid);
}

Compilation message (stderr)

domino.cpp: In member function 'void Graph::print()':
domino.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i = 0; i < adj.size(); i++) {
      |                         ~~^~~~~~~~~~~~
domino.cpp:21:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             for (int j = 0; j < adj.size(); j++) {
      |                             ~~^~~~~~~~~~~~
domino.cpp: In function 'Graph compress(std::vector<Edges>, std::vector<std::vector<int> >)':
domino.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
domino.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
domino.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j = 0; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
domino.cpp: In function 'int main()':
domino.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~
domino.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edges>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 0; i < m.size(); i++) {
      |                     ~~^~~~~~~~~~

• 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