Submission #910986

#	Time	Username	Problem	Language	Result	Execution time	Memory
910986		CyberCow	Trobojnica (COCI19_trobojnica)	C++17	110 / 110	54 ms	10684 KiB

trobojnica

#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 (stderr)

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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50