oj.uz

Submission #391479

# Submission time Handle Problem Language Result Execution time Memory
391479 2021-04-18T21:16:48 Z asbsfds Zagonetka (COI18_zagonetka) C++14
100 / 100
 579 ms 452 KB 
#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

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

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 328 KB Output is correct
2 Correct 107 ms 332 KB Output is correct
3 Correct 135 ms 340 KB Output is correct
4 Correct 151 ms 336 KB Output is correct
5 Correct 21 ms 328 KB Output is correct
6 Correct 160 ms 448 KB Output is correct
7 Correct 12 ms 200 KB Output is correct
8 Correct 16 ms 328 KB Output is correct
9 Correct 116 ms 344 KB Output is correct
10 Correct 46 ms 336 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 10 ms 328 KB Output is correct
4 Correct 11 ms 328 KB Output is correct
5 Correct 4 ms 324 KB Output is correct
6 Correct 8 ms 328 KB Output is correct
7 Correct 6 ms 328 KB Output is correct
8 Correct 12 ms 200 KB Output is correct
9 Correct 10 ms 328 KB Output is correct
10 Correct 3 ms 320 KB Output is correct
11 Correct 12 ms 328 KB Output is correct
12 Correct 10 ms 292 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 360 KB Output is correct
2 Correct 579 ms 368 KB Output is correct
3 Correct 423 ms 356 KB Output is correct
4 Correct 13 ms 328 KB Output is correct
5 Correct 17 ms 368 KB Output is correct
6 Correct 20 ms 328 KB Output is correct
7 Correct 110 ms 356 KB Output is correct
8 Correct 199 ms 328 KB Output is correct
9 Correct 164 ms 364 KB Output is correct
10 Correct 578 ms 452 KB Output is correct
11 Correct 457 ms 372 KB Output is correct
12 Correct 453 ms 356 KB Output is correct
13 Correct 534 ms 380 KB Output is correct
14 Correct 483 ms 372 KB Output is correct
15 Correct 575 ms 364 KB Output is correct
16 Correct 483 ms 364 KB Output is correct