oj.uz

Submission #959603

# Submission time Handle Problem Language Result Execution time Memory
959603 2024-04-08T13:40:00 Z lovrot Zagonetka (COI18_zagonetka) C++17
18 / 100
 43 ms 436 KB 
#include <cstdio> 
#include <vector> 
#include <algorithm> 
#include <cstring>
#include <cassert>

#define PB push_back

using namespace std;

const int N = 110;

int n;
vector<int> P;

int I[N], BIO[N], ANS[N];
vector<int> IN[N], OUT[N], G[N];

void topo(int u, bool d, int b, vector<int> &T) { // d = 1 : od vecih prema manjim
	if(BIO[u] || (d == 1 && u < b) || (d == 0 && u > b)) return;
	BIO[u] = 1;
	for(int v : G[u]) 
		if((u > v) == d) topo(v, d, b, T);
	T.PB(u);
}

bool query(vector<int> &V) {
	printf("query ");
	for(int x : V) printf("%d ", x);
	printf("\n");
	fflush(stdout);

	int x; scanf("%d", &x); return x;
}

void dfs(int u, vector<int> *D, vector<int> &T) {
	if(BIO[u]) return;
	BIO[u] = 1;
	for(int v : D[u]) dfs(v, D, T);
	T.PB(u);
}

void solve(vector<int> *D, vector<int> &F) {
	memset(BIO, 0, sizeof(BIO));
	vector<int> T; 

	for(int i = 0, j = 0; i < n; ++i) {
		T.clear();
		dfs(i, D, T);
		for(int x : T) {
			assert(j < F.size());
			ANS[x] = F[j++];
		}
	}

	for(int i = 0; i < n; ++i) printf("%d%c", ANS[i], " \n"[i == n - 1]);
}

int main() {
	scanf("%d", &n); 
	for(int i = 0; i < n; ++i) {
		int x; scanf("%d", &x); 
		P.PB(x);
		I[x] = i;
	}

	for(int i = 1; i < n; ++i) 
		for(int j = 1; j + i <= n; ++j) {
			memset(BIO, 0, sizeof(BIO));
			vector<int> Q = P, L, R;

			topo(j, 0, j + i, L); reverse(L.begin(), L.end());
			topo(j + i, 1, j, R); 
		
			int l = L.size(), r = R.size();
			if(l == i + 1) continue;
			for(int k = 0; k < min(l, r); ++k) {
				Q[I[L[l - k - 1]]] = R[r - k - 1];
				Q[I[R[k]]] = L[k];
			}
			if(l <= r) {
				for(int k = 0; k < r - l; ++k) Q[I[R[k + r - l]]] = R[k];
			} else {
				for(int k = 0; k < l - r; ++k) Q[I[L[k]]] = L[k + l - r];
			}

			if(!query(Q)) {
				G[j].PB(j + i);
				G[j + i].PB(j);
				OUT[I[j + i]].PB(I[j]);
				IN[I[j]].PB(I[j + i]);
			}
		}
	
	printf("end\n");
	
	vector<int> F;
	for(int i = 1; i <= n; ++i) F.PB(i);

	solve(OUT, F);
	reverse(F.begin(), F.end());
	solve(IN, F);
	fflush(stdout);
	return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from zagonetka.cpp:5:
zagonetka.cpp: In function 'void solve(std::vector<int>*, std::vector<int>&)':
zagonetka.cpp:51:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    assert(j < F.size());
      |           ~~^~~~~~~~~~
zagonetka.cpp: In function 'bool query(std::vector<int>&)':
zagonetka.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  int x; scanf("%d", &x); return x;
      |         ~~~~~^~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
zagonetka.cpp:62:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 0 ms 428 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 16 ms 344 KB Output is correct
3 Correct 22 ms 344 KB Output is correct
4 Correct 22 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 24 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 22 ms 344 KB Output is correct
10 Correct 8 ms 344 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 436 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 412 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -