Submission #1004351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004351		fuad27	Trobojnica (COCI19_trobojnica)	C++17	110 / 110	901 ms	46084 KiB

trobojnica

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