Submission #391479

#	Time	Username	Problem	Language	Result	Execution time	Memory
391479		asbsfds	Zagonetka (COI18_zagonetka)	C++14	100 / 100	579 ms	452 KiB

zagonetka

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 210;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n;
int niz[maxn];
int wh[maxn][maxn];
int sol[maxn];
int cnt[maxn];

vector< int > sorr() {
	queue< int > q;
	for (int i = 0; i < n; i++) {
		cnt[i] = 0;
		for (int j = 0; j < n; j++) {
			if (wh[j][i] > 0) cnt[i]++;
		}
		if (cnt[i] == 0) q.push(i);
	}
	
	vector< int > v;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		
		v.push_back(x);
		for (int i = 0; i < n; i++) {
			if (wh[x][i] > 0) {
				cnt[i]--;
				if (cnt[i] == 0) {
					q.push(i);
				}
			}
		}
	}
	assert(v.size() == n);
	return v;
}

pair<int, int> fin() {
	vector< int > v = sorr();
	
	//printf("sort: ");
	//for (int i = 0; i < v.size(); i++) printf("%d ", v[i]);
	//printf("\n");
	
	assert(v.size() == n);
	for (int i = 0; i < n; i++) {
		int a = v[i];
		for (int j = i - 1; j >= 0; j--) {
			int b = v[j];
			if (wh[b][a] == 1) return make_pair(b, a);
		}
	}
	return make_pair(-1, -1);
}

void gen1(vector< int > v, int a, int b) {
	if (v.size() == 0) return;
	int x = v[0];
	
	vector< int > p, q;
	for (int i = 1; i < v.size(); i++) {
		int tren = v[i];
		if (wh[tren][x] > 0) p.push_back(tren);
		else q.push_back(tren);
	}
	sol[x] = a + p.size();
	gen1(p, a, a + p.size() - 1);
	gen1(q, a + p.size() + 1, b);
}

void gen2(vector< int > v, int a, int b) {
	if (v.size() == 0) return;
	int x = v[0];
	
	vector< int > p, q;
	for (int i = 1; i < v.size(); i++) {
		int tren = v[i];
		if (wh[x][tren] > 0) p.push_back(tren);
		else q.push_back(tren);
	}
	sol[x] = b - p.size();
	gen2(p, sol[x] + 1, b);
	gen2(q, a, sol[x] - 1);
}

int query(int x, int y) {
	wh[x][y] = 0, wh[y][x] = 1;
	
	//vector< int > s;
	//for (int i = 0; i < n; i++) s.push_back(i);
	//gen1(s, 1, n);
	
	vector< int > v = sorr();
	for (int i = 0; i < n; i++) sol[v[i]] = i + 1;
	
	printf("query ");
	for (int i = 0; i < n; i++) printf("%d ", sol[i]);
	printf("\n");
	fflush(stdout);
	
	wh[x][y] = 1, wh[y][x] = 0;
	int out;
	scanf("%d", &out);
	return out;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", niz+i);
		
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (niz[i] < niz[j]) wh[i][j] = 1;
		}
	}
	
	/**
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			printf("%d ", wh[i][j]);
		printf("\n");
	}
	**/
	while (true) {
		pair<int, int> tr = fin();
		int x = tr.X;
		int y = tr.Y;
		
		if (x == -1) break;
		
		//printf("trying: %d %d\n", x + 1, y + 1);
		int out = query(x, y);
		
		if (out == 0) {
			//printf("confirmed %d %d\n", x + 1, y + 1);
			wh[x][y] = 2;
			for (int i = 0; i < n; i++) {
				if (wh[i][x] == 2) wh[i][y] = 2;
			}
			for (int i = 0; i < n; i++) {
				if (wh[y][i] == 2) wh[x][i] = 2;
			}
			
			for (int i = 0; i < n; i++) {
				if (wh[i][x] != 2) continue;
				for (int j = 0; j < n; j++) {
					if (wh[y][j] == 2) wh[i][j] = 2;
				}
			}
		} else {
			wh[x][y] = 0;
		}
		
		/**
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				printf("%d ", wh[i][j]);
			printf("\n");
		}
		**/
	}
	
	/**
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (wh[i][j] == 2) printf("%d %d\n", i + 1, j + 1);
		}
	}
	**/
	
	vector< int > s;
	for (int i = 0; i < n; i++) s.push_back(i);
	gen1(s, 1, n);
	
	printf("end\n");
	for (int i = 0; i < n; i++) printf("%d ", sol[i]);
	printf("\n");
	
	gen2(s, 1, n);
	for (int i = 0; i < n; i++) printf("%d ", sol[i]);
	printf("\n");
	fflush(stdout);
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from zagonetka.cpp:1:
zagonetka.cpp: In function 'std::vector<int> sorr()':
zagonetka.cpp:47:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  assert(v.size() == n);
      |         ~~~~~~~~~^~~~
zagonetka.cpp: In function 'std::pair<int, int> fin()':
zagonetka.cpp:58:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |  assert(v.size() == n);
      |         ~~~~~~~~~^~~~
zagonetka.cpp: In function 'void gen1(std::vector<int>, int, int)':
zagonetka.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
zagonetka.cpp: In function 'void gen2(std::vector<int>, int, int)':
zagonetka.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
zagonetka.cpp: In function 'int query(int, int)':
zagonetka.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |  scanf("%d", &out);
      |  ~~~~~^~~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
zagonetka.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |   scanf("%d", niz+i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51