Submission #465397

#	Time	Username	Problem	Language	Result	Execution time	Memory
465397		penguinhacker	Trobojnica (COCI19_trobojnica)	C++14	0 / 110	1 ms	332 KiB

trobojnica

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, nxt[mxN], prv[mxN];
string s;
bool rem[mxN];
vector<ar<int, 3>> ans;

bool ck(int i) {
	return !rem[i]&&s[prv[i]]!=s[i]&&ans.size()<n-3;
}

void solve(int i) {
	//cout << i << " " << prv[i] << " " << nxt[i] << endl;
	assert(ck(i));
	rem[i]=1;
	nxt[prv[i]]=nxt[i];
	prv[nxt[i]]=prv[i];
	for (char c : {'1', '2', '3'})
		if (s[prv[i]]!=c&&s[i]!=c) {
			s[prv[i]]=c;
			ans.push_back({prv[i], nxt[i], c-'0'});
			break;
		}
	if (ck(prv[i]))
		solve(prv[i]);
	if (ck(nxt[i]))
		solve(nxt[i]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for (int i=0; i<n; ++i) {
		nxt[i]=(i+1)%n;
		prv[i]=(i+n-1)%n;
	}
	for (int i=0; i<n; ++i)
		if (ck(i))
			solve(i);
	vector<int> v;
	for (int i=0; i<n; ++i)
		if (!rem[i])
			v.push_back(i);
	if (v.size()!=3||s[v[0]]==s[v[1]]||s[v[0]]==s[v[2]]||s[v[1]]==s[v[2]]) {
		cout << "NE";
		return 0;
	}
	assert(ans.size()==n-3);
	cout << "DA\n";
	for (ar<int, 3> a : ans)
		cout << a[0]+1 << " " << a[1]+1 << " " << a[2] << "\n";
	return 0;
}

Compilation message (stderr)

trobojnica.cpp: In function 'bool ck(int)':
trobojnica.cpp:14:45: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |  return !rem[i]&&s[prv[i]]!=s[i]&&ans.size()<n-3;
      |                                   ~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from trobojnica.cpp:1:
trobojnica.cpp: In function 'int main()':
trobojnica.cpp:54:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |  assert(ans.size()==n-3);
      |         ~~~~~~~~~~^~~~~

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