Submission #1004373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004373		aykhn	Trobojnica (COCI19_trobojnica)	C++17	60 / 110	2080 ms	13152 KiB

trobojnica

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds; 
using namespace std;

template<class T> using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 20 + 5;
const int mod = 1e9 + 7;
const int LOG = 20;
 
int n;
vector<array<int, 3>> res;
os<array<int, 3>> s;

int ok()
{
  if (s.size() == 3)
  {
    array<int, 3> x = *s.begin(), y = *next(s.begin()), z = *next(next(s.begin()));
    return x[2] != y[2] && x[2] != z[2] && y[2] != z[2];
  }
  int cnt = 0;
  for (int i = 0; i < s.size(); i++)
  {
    auto x = s.find_by_order(i);
    auto y = (next(x) == s.end() ? s.begin() : next(x));
    array<int, 3> A = *x, B = *y;
    if (A[2] != B[2])
    {
      s.erase(A), s.erase(B);
      s.insert({A[0], B[1], 6 - A[2] - B[2]});
      if (ok())
      {
        res.push_back({A[0], B[1], 6 - A[2] - B[2]});
        return 1;
      }
      s.erase({A[0], B[1], 6 - A[2] - B[2]});
      s.insert(A), s.insert(B);
    }
  }
  return 0;
}
 
 
signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  vector<array<int, 3>> v;
  int cnt[3] = {0, 0, 0};
  for (int i = 0; i < n; i++)
  {
    char ch;
    cin >> ch;
    s.insert({i + 1, (i + 1) % n + 1, ch - '0'});
    cnt[ch - '0' - 1]++;
  }
  if (cnt[0] % 2 != cnt[1] % 2 || cnt[0] % 2 != cnt[1] % 2 || cnt[1] % 2 != cnt[2] % 2)
  {
    cout << "NE\n";
    return 0;
  }
  if (!ok()) cout << "NE\n";
  else
  {
    cout << "DA\n";
    for (array<int, 3> &x : res) cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
  }
}

Compilation message (stderr)

trobojnica.cpp: In function 'int ok()':
trobojnica.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::bin_search_tree_set<std::array<int, 3>, __gnu_pbds::null_type, std::less<std::array<int, 3> >, __gnu_pbds::detail::tree_traits<std::array<int, 3>, __gnu_pbds::null_type, std::less<std::array<int, 3> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int i = 0; i < s.size(); i++)
      |                   ~~^~~~~~~~~~
trobojnica.cpp:27:7: warning: unused variable 'cnt' [-Wunused-variable]
   27 |   int cnt = 0;
      |       ^~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50