oj.uz

Submission #130206

# Submission time Handle Problem Language Result Execution time Memory
130206 2019-07-14T09:00:19 Z tjd229 Zagonetka (COI18_zagonetka) C++14
0 / 100
 91 ms 392 KB 
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int s[101], l[101];
int p[101];
int mat[101][101];
int pos[101];
int n;
int tp_sort(queue<int> &q,int s,int *vt,int *ind,vector<int> edge[101]) {
	int vis = 0;
	
	while (q.size()) {
		int u= q.front(); q.pop();
		vt[u] = s++;
		++vis;
		for (auto v : edge[u]) {
			if (--ind[v]==0) 
				q.push(v);			
		}
	}
	return vis;
}
void qry(int x,int y) {//chk pos[x]->pos[y]
	//inv edge ok -> no condition
	//inv edge no -> there is condition 
	//cycle -> there is cond.(inclusive indirect)
	vector<int> edge[101];
	vector<int> loc;
	int ind[101] = { 0 };
	int myp[101] = {};
	for (int i = 1; i <= n; ++i) myp[i] = p[i];
	for (int i = x; i <= y; ++i) loc.push_back(pos[i]);
	for (int i = 0; i < loc.size(); ++i) {
		for (int j = i + 1; j < loc.size(); ++j) {
			if (mat[loc[i]][loc[j]]) {
				edge[loc[i]].push_back(loc[j]);
				++ind[loc[j]];
			}
		}
	}
	edge[pos[y]].push_back(pos[x]);//inv edge
	++ind[pos[x]];
	queue<int> q;
	for (auto v : loc) {
		if (ind[v] == 0) q.push(v);
	}
	if (y - x + 1 == tp_sort(q,x, myp, ind, edge)) {
		int i;
		for (printf("query"), i = 1; i <= n; ++i) printf(" %d",myp[i]);
		printf("\n"); fflush(stdout);
		scanf("%d",&i);
		
		if (i) return;
	}
	//cycle chk
	mat[pos[x]][pos[y]] = 1;
}
int main() {
	int i;
	for (scanf("%d", &n), i = 1; i <= n; ++i) {
		scanf("%d", p + i);
		pos[p[i]] = i;
	}
	for (int range = 1; range < n; ++range) {
		for (i = 1; i + range <= n; ++i) qry(i,i+range);
	}
	vector<int> edge[101];
	queue<int> q;
	int ind[101] = { 0 };
	for (i = 1; i <= n; ++i) {
		for (int j = 1; j < i; ++j) {
			if (mat[i][j]) {
				edge[i].push_back(j);
				++ind[j];
			}
		}
	}
	int src = 1;
	for (i = 1; i <= n; ++i) {
		if (ind[i] == 0) {
			q.push(i);
			src+=tp_sort(q,src,s,ind,edge);
		}
	}

	for (i = 1; i <= n; ++i) ind[i] = 0;
	for (i = 1; i <= n; ++i) {
		edge[i].clear();
		for (int j = i+1; j <= n; ++j) {
			if (mat[i][j]) {
				edge[i].push_back(j);
				++ind[j];
			}
		}
	}
	src = 1;
	for (i = n; i >0; --i) {
		if (ind[i] == 0) {
			q.push(i);
			src += tp_sort(q, src, l, ind, edge);
		}
	}
	for (printf("end\n"), i = 1; i <= n; ++i) printf("%d ",s[i]);
	for (printf("\n"), i = 1; i <= n; ++i) printf("%d ", l[i]);
	fflush(stdout);
	return 0;
}

Compilation message

zagonetka.cpp: In function 'void qry(int, int)':
zagonetka.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < loc.size(); ++i) {
                  ~~^~~~~~~~~~~~
zagonetka.cpp:35:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j < loc.size(); ++j) {
                       ~~^~~~~~~~~~~~
zagonetka.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&i);
   ~~~~~^~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:61:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (scanf("%d", &n), i = 1; i <= n; ++i) {
       ~~~~~~~~~~~~~~~^~~~~~~
zagonetka.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", p + i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 248 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 268 KB Output is correct
2 Incorrect 31 ms 248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -