oj.uz

Submission #223531

# Submission time Handle Problem Language Result Execution time Memory
223531 2020-04-15T10:58:51 Z maomao90 Checker (COCI19_checker) C++14
0 / 110
 3000 ms 6008 KB 
#include <cstdio>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <tuple>
#include <cmath>
#include <cassert>

using namespace std;

typedef pair <int, int> ii;
typedef pair <ii, int> iii;

struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator() (const std::pair<T1, T2> &pair) const
	{
		return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	}
};

int tc;
int N;
char temps[200005];
iii diagonals[200005];
//unordered_map <ii, int, pair_hash> colours;
bool isInvalid[200005];
ii impt1[200005], impt2[200005];

bool comp(iii right, iii left)
{
    int rx, ry, lx, ly;
    tie(rx, ry) = right.first; tie(lx, ly) = left.first;
    if (abs(rx - ry) < abs(lx - ly)) return true;
    else if (abs(rx - ry) == abs(lx - ly))
    {
        if (rx < ry) return true;
    }
    return false;
}

int main()
{
    scanf("%d%d", &tc, &N);
    scanf(" %s", temps);
    for (int i = 1; i <= N; i++)
    {
        char temp = temps[i - 1];
        /*
        if (i == N)
        {
            colours[ii(i, 1)] = (int) temp - '0';
            colours[ii(1, i)] = (int) temp - '0';
        }
        else
        {
            colours[ii(i, i + 1)] = (int) temp - '0';
            colours[ii(i + 1, i)] = (int) temp - '0';
        }
        */
        if (i == N)
        {
            impt1[i] = ii(1, temp - '0');
            impt2[1] = ii(i, temp - '0');
        }
        else
        {
            impt1[i] = ii(i + 1, temp - '0');
            impt2[i + 1] = ii(i, temp - '0');
        }
    }
    for (int i = 0; i < N - 3; i++)
    {
        int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
        if (X > Y) swap(X, Y);
        diagonals[i] = iii(ii(X, Y), C);
        /*
        colours[ii(X, Y)] = C;
        colours[ii(Y, X)] = C;
        */
    }
    sort(diagonals, diagonals + N - 3, comp);
    assert(1 == 2);
    for (int i = 0; i < N - 3; i++)
    {
        int x, y, c;
        tie(x, y) = diagonals[i].first; c = diagonals[i].second;
        if (isInvalid[x] || isInvalid[y])
        {
            printf("neispravna triangulacija\n");
            return 0;
        }
        int impt;
        if (impt1[x].first == impt1[y].first || impt1[x].first == impt2[y].first) impt = impt1[x].first;
        else impt = impt2[x].first;
        isInvalid[impt] = true;
        if (impt1[x].first == impt) impt1[x] = ii(y, c);
        else impt2[x] = ii(y, c);
        if (impt1[y].first == impt) impt1[y] = ii(x, c);
        else impt2[y] = ii(x, c);
    }
    for (int i = 1; i <= N; i++)
    {
        char temp = temps[i - 1];
        /*
        if (i == N)
        {
            colours[ii(i, 1)] = (int) temp - '0';
            colours[ii(1, i)] = (int) temp - '0';
        }
        else
        {
            colours[ii(i, i + 1)] = (int) temp - '0';
            colours[ii(i + 1, i)] = (int) temp - '0';
        }
        */
        if (i == N)
        {
            impt1[i] = ii(1, temp - '0');
            impt2[1] = ii(i, temp - '0');
        }
        else
        {
            impt1[i] = ii(i + 1, temp - '0');
            impt2[i + 1] = ii(i, temp - '0');
        }
    }
    for (int i = 0; i < N - 3; i++)
    {
        int x, y, c;
        tie(x, y) = diagonals[i].first; c = diagonals[i].second;
        int impt, c1, c2;
        if (impt1[x].first == impt1[y].first || impt1[x].first == impt2[y].first)
        {
            impt = impt1[x].first;
            c1 = impt1[x].second;
            c2 = impt1[y].first == impt ? impt1[y].second : impt2[y].second;
        }
        else
        {
            impt = impt2[x].first;
            c1 = impt2[x].second;
            c2 = impt1[y].first == impt ? impt1[y].second : impt2[y].second;
        }

        if (c == c1 || c == c2 || c1 == c2)
        {
            printf("neispravno bojenje\n");
            return 0;
        }

        if (impt1[x].first == impt) impt1[x] = ii(y, c);
        else impt2[x] = ii(y, c);
        if (impt1[y].first == impt) impt1[y] = ii(x, c);
        else impt2[y] = ii(x, c);
    }
    printf("tocno\n");
    return 0;
}

Compilation message

checker.cpp: In function 'int main()':
checker.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &tc, &N);
     ~~~~~^~~~~~~~~~~~~~~~~
checker.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", temps);
     ~~~~~^~~~~~~~~~~~~~
checker.cpp:75:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 6008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 6008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -