oj.uz

Submission #1004427

# Submission time Handle Problem Language Result Execution time Memory
1004427 2024-06-21T08:50:34 Z aykhn Trobojnica (COCI19_trobojnica) C++17
110 / 110
 352 ms 51628 KB 
#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;
queue<array<array<int, 3>, 2>> del[4];
int cnt[4];

int ok()
{
  if (s.size() == 3)
  {
    return cnt[1] == 1 && cnt[2] == 1 && cnt[3] == 1;
  }
  if (max({cnt[1], cnt[2], cnt[3]}) == s.size())
  {
    return 0;
  }
  int mx = 1;
  for (int i = 1; i <= 3; i++) if (cnt[i] > cnt[mx]) mx = i;
  while (!del[mx].empty())
  {
    if (s.find(del[mx].front()[0]) == s.end() || s.find(del[mx].front()[1]) == s.end()) del[mx].pop();
    else break;
  }
  assert(!del[mx].empty());
  array<array<int, 3>, 2> d = del[mx].front();
  del[mx].pop();
  s.erase(d[0]);
  cnt[d[0][2]]--;
  s.erase(d[1]);
  cnt[d[1][2]]--;
  s.insert({d[0][0], d[1][1], 6 - d[0][2] - d[1][2]});
  cnt[6 - d[0][2] - d[1][2]]++;
  auto x = s.find({d[0][0], d[1][1], 6 - d[0][2] - d[1][2]});
  auto z = (x == s.begin() ? prev(s.end()) : prev(x));
  auto y = (next(x) == s.end() ? s.begin() : next(x));
  array<int, 3> A = *z, B = *x, C = *y;
  if (A[2] != B[2])
  {
    del[A[2]].push({A, B});
    del[B[2]].push({A, B});
  }
  if (B[2] != C[2])
  {
    del[B[2]].push({B, C});
    del[C[2]].push({B, C});
  }
  if (ok())
  {
    res.push_back({d[0][0], d[1][1], 6 - d[0][2] - d[1][2]});
    return 1;
  }
  
  return 0;
}
 
 
signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  vector<array<int, 3>> v;
  for (int i = 0; i < n; i++)
  {
    char ch;
    cin >> ch;
    s.insert({i + 1, (i + 1) % n + 1, ch - '0'});
    cnt[ch - '0']++;
  }
  for (auto x = s.begin(); x != s.end(); x++)
  {
    auto y = (next(x) == s.end() ? s.begin() : next(x));
    if ((*x)[2] != (*y)[2]) del[(*x)[2]].push({*x, *y});
  }
  if (cnt[3] % 2 != cnt[1] % 2 || cnt[3] % 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

trobojnica.cpp: In function 'int ok()':
trobojnica.cpp:28:37: 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 |   if (max({cnt[1], cnt[2], cnt[3]}) == s.size())
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 508 KB Output is correct
21 Correct 333 ms 46928 KB Output is correct
22 Correct 310 ms 48704 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 352 ms 51628 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 171 ms 26196 KB Output is correct
28 Correct 128 ms 16208 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 120 ms 13140 KB Output is correct