oj.uz

Submission #910986

# Submission time Handle Problem Language Result Execution time Memory
910986 2024-01-18T10:40:49 Z CyberCow Trobojnica (COCI19_trobojnica) C++17
110 / 110
 54 ms 10684 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];
pair<int, int> nax[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] };
        nax[i + 2] = { i + 1 , v[i] };
    }
    gn[n] = { 1, v[n - 1] };
    nax[1] = { n, v[n - 1] };
    int qan = 0, gag = n;
    vector<pair<int, pair<int, int>>> ans;
    while (qan < n - 3)
    {
        while (gn[gag].second == nax[gag].second || !(abc[gn[gag].second] == max(a, max(b, c)) || abc[nax[gag].second] == max(a, max(b, c))))
        {
            gag = gn[gag].first;
        }
        qan++;
        if (gn[gag].second != 1 && nax[gag].second != 1)
        {
            ans.push_back({ 1, {nax[gag].first, gn[gag].first}});
            a++; b--; c--;
            abc[1]++;
            abc[2]--;
            abc[3]--;
            gn[nax[gag].first].second = 1;
            gn[nax[gag].first].first = gn[gag].first;
            nax[gn[gag].first].second = 1;
            nax[gn[gag].first].first = nax[gag].first;
        }
        else if (gn[gag].second != 2 && nax[gag].second != 2)
        {
            ans.push_back({ 2, {nax[gag].first, gn[gag].first} });
            a--; b++; c--;
            abc[1]--;
            abc[2]++;
            abc[3]--;
            gn[nax[gag].first].second = 2;
            gn[nax[gag].first].first = gn[gag].first;
            nax[gn[gag].first].second = 2;
            nax[gn[gag].first].first = nax[gag].first;
        }
        else if (gn[gag].second != 3 && nax[gag].second != 3)
        {
            ans.push_back({ 3, {nax[gag].first, gn[gag].first} });
            a--; b--; c++;
            abc[1]--;
            abc[2]--;
            abc[3]++;
            gn[nax[gag].first].second = 3;
            gn[nax[gag].first].first = gn[gag].first;
            nax[gn[gag].first].second = 3;
            nax[gn[gag].first].first = nax[gag].first;
        }
        gag = nax[gag].first;
    }
    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:123: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]
  123 |     for ( i = 0; i < ans.size(); i++)
      |                  ~~^~~~~~~~~~~~
trobojnica.cpp:36:15: warning: unused variable 'j' [-Wunused-variable]
   36 |     int n, i, j, x, y;
      |               ^
trobojnica.cpp:36:18: warning: unused variable 'x' [-Wunused-variable]
   36 |     int n, i, j, x, y;
      |                  ^
trobojnica.cpp:36:21: warning: unused variable 'y' [-Wunused-variable]
   36 |     int n, i, j, x, y;
      |                     ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2524 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2524 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2524 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 43 ms 10684 KB Output is correct
22 Correct 41 ms 9668 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 54 ms 10568 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 25 ms 6264 KB Output is correct
28 Correct 5 ms 1756 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 3 ms 1632 KB Output is correct