Submission #102594

#	Time	Username	Problem	Language	Result	Execution time	Memory
102594		UncleGrandpa925	Hidden Sequence (info1cup18_hidden)	C++17	100 / 100	150 ms	512 KiB

hidden

/*input
20
*/
#include <bits/stdc++.h>
#ifndef UncleGrandpa
#include "grader.h"
#endif
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define __builtin_popcount __builtin_popcountll
#define bit(x,y) ((x>>y)&1LL)
#define loop(i,l,r) for(int i=(int)l; i<=(int)r; i++)
#define rloop(i,l,r) for(int i=(int)l; i>=(int)r; i--)
//const int N=;
#ifdef UncleGrandpa
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
	return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
	os << '[';
	for (unsigned int i = 0; i < a.size(); i++)
		os << a[i] << (i < a.size() - 1 ? ", " : "");
	os << ']';
	return os;
}
int read() {
	int x; cin >> x; return x;
}
vector<int> ORI;
bool isSubsequence(vector<int> inp) {
	assert(inp.size() <= ORI.size() / 2 + 1);
	int it = 0;
	loop(i, 0, ORI.size() - 1) {
		if (it == inp.size()) return true;
		it += (inp[it] == ORI[i]);
	}
	return (it == inp.size());
}

#endif

vector<int> findSequence(int _n) {
	int n = _n;
	pair<int, int> num = mp(0, 0);
	loop(i, 0, 1) {
		vector<int> cur;
		loop(k, 1, n / 2 + 1) {
			cur.push_back(i);
			if (!isSubsequence(cur)) {
				num = mp(i, k - 1);
				break;
			}
		}
	}
	if (num.se == 0) {
		vector<int> ret(n, num.fi ^ 1);
		return ret;
	}
	vector<int> conseq(num.se + 1, 0);
	loop(k, 1, num.se) {
		int leftX = k - 1;
		int rightX = num.se - k;
		bool done = false;
		loop(curl, 1, n / 2 - rightX) {
			vector<int> cur;
			loop(_, 1, curl) cur.push_back(num.fi ^ 1);
			loop(_, 1, rightX + 1) cur.push_back(num.fi);
			if (!isSubsequence(cur)) {
				done = true;
				conseq[k] = curl - 1;
				break;
			}
		}
		if (done) continue;
		loop(curr, 1, n / 2 - leftX) {
			vector<int> cur;
			loop(_, 1, leftX + 1) cur.push_back(num.fi);
			loop(_, 1, curr) cur.push_back(num.fi ^ 1);
			if (!isSubsequence(cur)) {
				done = true;
				conseq[k] = n - num.se - (curr - 1);
				break;
			}
		}
		if (!done)
			conseq[k] = n - num.se - (n / 2 - leftX);
	}
	vector<int> ret;
	loop(i, 1, num.se) {
		loop(_, 1, conseq[i] - conseq[i - 1]) ret.push_back(num.fi ^ 1);
		ret.push_back(num.fi);
	}
	while (ret.size() < n) ret.push_back(num.fi ^ 1);
	return ret;
}

#ifdef UncleGrandpa
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
	int n = rd() % 1000 + 1;
	// // cin >> n;
	loop(i, 1, n) ORI.push_back(rd() % 2);
	// cout << ORI << endl;
	auto rec = findSequence(n);
	if (rec == ORI) cout << "OK" << endl;
	else {
		cout << "WA" << endl;
		cout << rec << endl << ORI << endl;
		assert(false);
	}
	cout << rec << endl << ORI << endl;
}
#endif

Compilation message (stderr)

hidden.cpp: In function 'std::vector<int> findSequence(int)':
hidden.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ret.size() < n) ret.push_back(num.fi ^ 1);
         ~~~~~~~~~~~^~~
grader.cpp: In function 'int main()':
grader.cpp:28:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     fprintf (fifo_out, "%d\n", ans.size ());
                                ~~~~~~~~~~~^
grader.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ans.size () && i < N; i++)
                   ~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80