oj.uz

Submission #542973

# Submission time Handle Problem Language Result Execution time Memory
542973 2022-03-28T14:56:15 Z Olympia Domino (COCI15_domino) C++17
0 / 160
 3191 ms 359808 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 22964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3181 ms 359808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1830 ms 346300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 746 ms 90272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3184 ms 359668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3191 ms 359604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3177 ms 359656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 758 ms 90252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3178 ms 359652 KB Output isn't correct
2 Halted 0 ms 0 KB -