oj.uz

Submission #1004351

# Submission time Handle Problem Language Result Execution time Memory
1004351 2024-06-21T08:11:52 Z fuad27 Trobojnica (COCI19_trobojnica) C++17
110 / 110
 901 ms 46084 KB 
#include <bits/stdc++.h>
using namespace std;
vector<array<int,3>> v;
set<array<int,3>> vals;
set<array<int,3>> best;
vector<array<int,3>> res;
map<array<int,2>, int> vls;
set<array<int,3>>::iterator nxt(set<array<int,3>>::iterator xx, set<array<int,3>>& ssss) {
  auto x=xx;
  x++;
  if(x == ssss.end()) {
    x=ssss.begin();
    return x;
  }
  return x;
}
set<array<int,3>>::iterator prv(set<array<int,3>>::iterator xx, set<array<int,3>>& ssss) {
  auto x=xx;
  if(x == ssss.begin())return --ssss.end();
  return (--x);
}
void recalc(array<int,3> idx) {
  auto it = vals.find(idx);
  auto it2 = nxt(it, vals);
  auto it3 = nxt(it2, vals);
  int val = 3;
  if((*it2)[2] != (*it)[2]) {
    val--;;
    if((1^2^3^(*it2)[2]^(*it)[2]) != (*it3)[2]) {
      val--;
    }
  }
  best.erase({vls[{idx[0], idx[1]}], idx[0], idx[1]});
  vls[{idx[0], idx[1]}] = val;
  best.insert({vls[{idx[0], idx[1]}], idx[0], idx[1]});
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  v.resize(n);
  string s;
  cin >> s;
  for(int i = 0;i<n;i++) {
    v[i][2] = (s[i]-'0');
    v[i][0] = i;
    v[i][1] = (i+1)%n;
  }
  vals=set<array<int,3>> (v.begin(), v.end());
  for(int i = 0;i<n;i++) {
    best.insert({3, i, (i+1)%n});
    vls[{i,(i+1)%n}]=3;
  }
  for(int i = 0;i<n;i++) {
    recalc(v[i]);
  }
  while(1) {
    if(vals.size() == 3)break;
    auto it = best.begin();
    if((*it)[0] == 3) {
      cout << "NE\n";
      return 0;
    }
    auto itv = vals.lower_bound({(*it)[1], (*it)[2], 0});
    auto itv2 = nxt(itv, vals);
    int F = (*itv)[0];
    int S = (*itv2)[1];
    int nwvl = (1^2^3^(*itv)[2]^(*itv2)[2]);
    res.push_back({F, S, nwvl});
    best.erase(it);
    best.erase({vls[{(*itv2)[0], (*itv2)[1]}], (*itv2)[0], (*itv2)[1]});
    vals.erase(itv);
    vals.erase(itv2);
    best.insert({3, F, S});
    vls[{F, S}]=3;
    vals.insert({F, S, nwvl});
    it = vals.find({F, S, nwvl});
    recalc((*it));
    recalc((*prv(it, vals)));
    recalc(*(prv(prv(it, vals),vals)));
  }
  int x=0;
  for(auto i:vals) {
    x^=i[2];
  }
  if(x!=0) {
    cout <<"NE\n";
    return 0;
  }
  cout << "DA\n";
  for(auto i:res)cout << i[0]+1 << " " << i[1]+1 << " " << i[2] <<  "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 761 ms 46084 KB Output is correct
22 Correct 843 ms 42812 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 869 ms 45640 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 401 ms 22980 KB Output is correct
28 Correct 901 ms 43784 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 315 ms 40612 KB Output is correct