oj.uz

Submission #1004355

# Submission time Handle Problem Language Result Execution time Memory
1004355 2024-06-21T08:12:14 Z aykhn Trobojnica (COCI19_trobojnica) C++17
60 / 110
 633 ms 524288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 20 + 5;
const int mod = 1e9 + 7;
const int LOG = 20;
 
int n;
vector<array<int, 3>> res;
 
int ok(vector<array<int, 3>> &v)
{
  if (v.size() == 3)
  {
    return v[0][0] != v[1][0] && v[0][0] != v[2][0] && v[1][0] != v[2][0];
  }
  int cnt = 0;
  for (int i = 0; i < v.size(); i++)
  {
    if (v[i][0] != v[(i + 1) % (int)v.size()][0])
    {
      vector<array<int, 3>> nw;
      for (int j = 0; j < v.size(); j++)
      {
        if (j != i && j != (i + 1) % (int)v.size())
        {
          nw.push_back(v[j]);
        }
        else if (j == i)
        {
          nw.push_back({6 - v[i][0] - v[(i + 1) % (int)v.size()][0], v[i][1], v[(i + 1) % (int)v.size()][2]});
        }
      }
      if (ok(nw))
      {
        res.push_back({v[i][1], v[(i + 1) % (int)v.size()][2], 6 - v[i][0] - v[(i + 1) % (int)v.size()][0]});
        return 1;
      }
    }
  }
  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;
    v.push_back({ch - '0', i + 1, (i + 1) % n + 1});
    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(v)) 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(std::vector<std::array<int, 3> >&)':
trobojnica.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = 0; i < v.size(); i++)
      |                   ~~^~~~~~~~~~
trobojnica.cpp:26:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |       for (int j = 0; j < v.size(); j++)
      |                       ~~^~~~~~~~~~
trobojnica.cpp:20:7: warning: unused variable 'cnt' [-Wunused-variable]
   20 |   int cnt = 0;
      |       ^~~

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 344 KB Output is correct
3 Correct 1 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 344 KB Output is correct
3 Correct 1 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 6 ms 8024 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 5 ms 8028 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 8028 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 7964 KB Output is correct

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 6 ms 8024 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 5 ms 8028 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 8028 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 7964 KB Output is correct
21 Runtime error 633 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -