oj.uz

Submission #144651

# Submission time Handle Problem Language Result Execution time Memory
144651 2019-08-17T10:15:47 Z emilem Zagonetka (COI18_zagonetka) C++14
9 / 100
 79 ms 504 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

template<typename T>
ostream& operator<<(ostream& ostr, const vector<T>& a)
{
	for (int i = 0; i < a.size(); ++i)
		ostr << a[i] << ' ';
	return ostr;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; ++i)
		cin >> p[i];
	if (n <= 6)
	{
		for (int i = 0; i < n; ++i)
			p[i] = i + 1;
		vector<int> small, large;
		do {
			cout << "query " << p << endl;
			int res;
			cin >> res;
			if (res && small.empty())
				small = p;
			if (res)
				large = p;
		} while (next_permutation(p.begin(), p.end()));
		cout << "end\n" << small << '\n' << large << endl;
		return 0;
	}
	else
	{
		
		int res;
		set<int> possible;
		for (int i = 0; i < n; ++i)
			possible.insert(i);
		for (int i = 0; i < n; ++i)
			for (int j = i + 1; j < n; ++j)
			{
				swap(p[i], p[j]);
				cout << "query " << p << endl;
				cin >> res;
				if (res)
				{
					if (possible.count(i)) possible.erase(i);
					if (possible.count(i)) possible.erase(j);
				}
				swap(p[i], p[j]);
			}
		
		vector<int> small(n), large(n);
		for (int ii = 0; ii < n; ++ii)
			small[ii] = large[ii] = ii + 1;
		reverse(large.begin(), large.end());
		int i = *possible.begin(), j = *(++possible.begin());
		if (possible.size() != 2)
			throw;
		// int i = 1, j = 3;
		if (i > j)
			/*throw*/swap(i, j);
		if (p[i] > p[j])
		{
			small[j] = small[i];
			if (small[i] == n)
				/*throw*/;
			++small[i];
			for (int k = i + 1; k < j; ++k)
				++small[k];
		}
		else
		{
			large[j] = large[i];
			--large[i];
			for (int k = i + 1; k < j; ++k)
				--large[k];
		}
		cout << "end\n" << small << '\n' << large << endl;
	}
}

Compilation message

zagonetka.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, const std::vector<T>&) [with T = int; std::ostream = std::basic_ostream<char>]':
zagonetka.cpp:31:24:   required from here
zagonetka.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 6 ms 248 KB Output is correct
6 Correct 9 ms 248 KB Output is correct
7 Correct 10 ms 248 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -