oj.uz

Submission #910968

# Submission time Handle Problem Language Result Execution time Memory
910968 2024-01-18T10:22:26 Z CyberCow Trobojnica (COCI19_trobojnica) C++17
60 / 110
 2000 ms 4024 KB 
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);

const ll N = 200005;

pair<int, int> gn[N];
int abc[5];

void solve()
{
    int n, i, j, x, y;
    cin >> n;
    char cc;
    int a = 0, b = 0, c = 0;
    vector<int> v;
    for ( i = 0; i < n; i++)
    {
        cin >> cc;
        if (cc == '1')
        {
            a++;
            v.push_back(1);
            abc[1]++;
        }
        else if (cc == '2')
        {
            b++;
            v.push_back(2);
            abc[2]++;
        }
        else
        {
            c++;
            v.push_back(3);
            abc[3]++;
        }
    }
    if (max(a, max(b, c)) == n || a % 2 != b % 2 || a % 2 != c % 2 || b % 2 != c % 2)
    {
        cout << "NE\n";
        return;
    }
    for ( i = 0; i < n - 1; i++)
    {
        gn[i + 1] = { i + 2, v[i] };
    }
    gn[n] = { 1, v[n - 1] };
    int qan = 0, gag = 1;
    vector<pair<int, pair<int, int>>> ans;
    while (qan < n - 3)
    {
        while (gn[gag].second == gn[gn[gag].first].second || !(abc[gn[gag].second] == max(a, max(b, c)) || abc[gn[gn[gag].first].second] == max(a, max(b, c))))
        {
            gag = gn[gag].first;
        }
        qan++;
        if (gn[gag].second != 1 && gn[gn[gag].first].second != 1)
        {
            ans.push_back({ 1, {gag, gn[gn[gag].first].first} });
            a++; b--; c--;
            abc[1]++;
            abc[2]--;
            abc[3]--;
            gn[gag].second = 1;
            gn[gag].first = gn[gn[gag].first].first;
            continue;
        }
        if (gn[gag].second != 2 && gn[gn[gag].first].second != 2)
        {
            ans.push_back({ 2, {gag, gn[gn[gag].first].first} });
            a--; b++; c--;
            abc[1]--;
            abc[2]++;
            abc[3]--;
            gn[gag].second = 2;
            gn[gag].first = gn[gn[gag].first].first;
            continue;
        }
        if (gn[gag].second != 3 && gn[gn[gag].first].second != 3)
        {
            ans.push_back({ 3, {gag, gn[gn[gag].first].first} });
            a--; b--; c++;
            abc[1]--;
            abc[2]--;
            abc[3]++;
            gn[gag].second = 3;
            gn[gag].first = gn[gn[gag].first].first;
            continue;
        }
    }
    cout << "DA\n";
    for ( i = 0; i < ans.size(); i++)
    {
        cout << ans[i].second.first << ' ' << ans[i].second.second << ' ' << ans[i].first << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message

trobojnica.cpp: In function 'void solve()':
trobojnica.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for ( i = 0; i < ans.size(); i++)
      |                  ~~^~~~~~~~~~~~
trobojnica.cpp:35:15: warning: unused variable 'j' [-Wunused-variable]
   35 |     int n, i, j, x, y;
      |               ^
trobojnica.cpp:35:18: warning: unused variable 'x' [-Wunused-variable]
   35 |     int n, i, j, x, y;
      |                  ^
trobojnica.cpp:35:21: warning: unused variable 'y' [-Wunused-variable]
   35 |     int n, i, j, x, y;
      |                     ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 496 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 496 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 496 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Execution timed out 2061 ms 4024 KB Time limit exceeded
22 Halted 0 ms 0 KB -