oj.uz

Submission #640673

# Submission time Handle Problem Language Result Execution time Memory
640673 2022-09-15T05:27:54 Z SanguineChameleon Zagonetka (COI18_zagonetka) C++14
100 / 100
 93 ms 336 KB 
// BEGIN BOILERPLATE CODE

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

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int ms = 1e2 + 20;
int a[ms];
int b[ms];
int c[ms];
int q[ms];
int p[ms];
bool g[ms];
vector<int> adj1[ms];
vector<int> adj2[ms];
vector<int> adj3[ms];
int dzi[ms];
int dzo[ms];
int mi[ms];
int ma[ms];
int lt, rt;
map<pair<int, int>, bool> e;
vector<int> pp;

void dfs(int u) {
	g[u] = true;
	for (auto v: adj1[u]) {
		if (!g[v] && lt <= v && v <= rt) {
			dfs(v);
		}
	}
	pp.push_back(u);
}

bool check() {
	for (auto x: e) {
		if (q[x.first.first] > q[x.first.second]) {
			return false;
		}
	}
	return true;
}

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p[a[i]] = i;
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 1; j + i <= n; j++) {
			lt = j;
			rt = j + i;
			pp.clear();
			for (int k = lt; k <= rt; k++) {
				g[k] = false;
			}
			dfs(rt);
			if (g[lt]) {
				continue;
			}
			for (int k = lt; k <= rt; k++) {
				if (!g[k]) {
					dfs(k);
				}
			}
			for (int i = 1; i <= lt - 1; i++) {
				b[i] = i;
			}
			for (int i = rt + 1; i <= n; i++) {
				b[i] = i;
			}
			for (int i = 0; i < (int)pp.size(); i++) {
				b[pp[i]] = lt + i;
			}
			for (int i = 1; i <= n; i++) {
				q[i] = b[a[i]];
			}
			cout << "query";
			for (int i = 1; i <= n; i++) {
				cout << " " << q[i];
			}
			cout << endl;
			int d;
			cin >> d;
			if (d == 0) {
				adj2[p[lt]].push_back(p[rt]);
				adj3[p[rt]].push_back(p[lt]);
				dzo[p[lt]]++;
				dzi[p[rt]]++;
				adj1[rt].push_back(lt);
			}
		}
	}
	set<int, greater<int>> s;
	for (int i = 1; i <= n; i++) {
		if (dzo[i] == 0) {
			s.insert(i);
		}
	}
	for (int i = n; i >= 1; i--) {
		int u = *s.begin();
		mi[u] = i;
		s.erase(u);
		for (auto v: adj3[u]) {
			dzo[v]--;
			if (dzo[v] == 0) {
				s.insert(v);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dzi[i] == 0) {
			s.insert(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		int u = *s.begin();
		ma[u] = i;
		s.erase(u);
		for (auto v: adj2[u]) {
			dzi[v]--;
			if (dzi[v] == 0) {
				s.insert(v);
			}
		}
	}
	cout << "end" << endl;
	for (int i = 1; i <= n - 1; i++) {
		cout << mi[i] << " ";
	}
	cout << mi[n];
	cout << endl;
	for (int i = 1; i <= n - 1; i++) {
		cout << ma[i] << " ";
	}
	cout << ma[n];
	cout << endl;
}

// END MAIN CODE

Compilation message

zagonetka.cpp: In function 'void file_io(std::string, std::string)':
zagonetka.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zagonetka.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 208 KB Output is correct
2 Correct 26 ms 328 KB Output is correct
3 Correct 34 ms 312 KB Output is correct
4 Correct 29 ms 328 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 29 ms 312 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 5 ms 208 KB Output is correct
9 Correct 33 ms 312 KB Output is correct
10 Correct 18 ms 208 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 208 KB Output is correct
8 Correct 4 ms 208 KB Output is correct
9 Correct 5 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 4 ms 208 KB Output is correct
12 Correct 4 ms 256 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 308 KB Output is correct
2 Correct 74 ms 208 KB Output is correct
3 Correct 63 ms 308 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 5 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 26 ms 324 KB Output is correct
9 Correct 24 ms 328 KB Output is correct
10 Correct 78 ms 312 KB Output is correct
11 Correct 52 ms 320 KB Output is correct
12 Correct 62 ms 312 KB Output is correct
13 Correct 76 ms 316 KB Output is correct
14 Correct 63 ms 312 KB Output is correct
15 Correct 83 ms 316 KB Output is correct
16 Correct 48 ms 316 KB Output is correct