oj.uz

Submission #465397

# Submission time Handle Problem Language Result Execution time Memory
465397 2021-08-15T20:41:34 Z penguinhacker Trobojnica (COCI19_trobojnica) C++14
0 / 110
 1 ms 332 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -