Submission #130411

#	Time	Username	Problem	Language	Result	Execution time	Memory
130411		tjd229	Zagonetka (COI18_zagonetka)	C++14	0 / 100	105 ms	400 KiB

zagonetka

#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 sign,d;
int tp_sort(queue<int> &q, int s, int *vt, int *ind, vector<int> edge[101], int debug = 0) {
	int vis = 0;
	//int sign = q.top() < 0 ? -1 : 1;
	while (q.size()) {
		int u = q.front(); q.pop();
		if (u < 0) u = -u;
		vt[u] = s++;
		++vis;
		if (debug) printf("v:%d\n", u);
		for (auto v : edge[u]) {
			if (--ind[v] == 0)
				q.push(v);
		}
	}
	return vis;
}
int dfs(int x, int dst, vector<int> edge[101]) {
	if (dst == x) return 1;
	for (auto nxt : edge[x]) {
		if (dfs(nxt, dst, edge)) return 1;
	}
	return 0;
}
void perm_sort(int root, int &num, int *vt, int *ind, vector<int> *edge, vector<int> *back) {
	//back tracking by q(limit)
	queue<int> q; q.push(root);
	priority_queue<int> pq;
	int src[101] = { 0 };
	//int d = -sign;
	while (q.size()) {
		int u = q.front(); q.pop();
		
		for (auto v : back[u]) {
			if (vt[v]) {
				++src[u];
				continue;
			}
			q.push(v);			
		}
		if (src[u] == ind[u]) pq.push(u*sign), src[u]++;
	}
	//tp sort by pq and forward edge
	
	while (pq.size()) {
		int x = pq.top(); pq.pop();
		x*=sign;
		vt[x] = num;
		num += d;
		for (auto v : edge[x]) {
			if (++src[v] == ind[v]) {
				pq.push(v*sign);
				//if (sign == 1) printf("%d->%d\n",x,v);
			}
		}
	}
	//assign
	//src,sign,assign num, vt, ind, edge,bk
}
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] = { 0 };
	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 = 0; j < loc.size(); ++j) {
			if (mat[loc[i]][loc[j]]) {
				edge[loc[i]].push_back(loc[j]);
				++ind[loc[j]];
			}
		}
	}
	//dfs chk
	if (dfs(pos[x], pos[y], edge)) {
		//printf("%d(%d)->%d(%d) ok\n",pos[x],x,pos[y],y);
		return;
	}

	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;
		i = 1;
		for (printf("query"), i = 1; i <= n; ++i) printf(" %d",myp[i]);
		printf("\n"); fflush(stdout);
		scanf("%d",&i);
		
		if (i) return;
	}

	//cycle chk
	//for (int i = 1; i <= n; ++i) printf("%d ", myp[i]);
	//printf("corr?,%d->%d\n", pos[x], pos[y]);
	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> back[101],edge[101];
	int ind[101] = { 0 };
	int bind[101] = { 0 };
	for (i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (mat[i][j]) {
				back[j].push_back(i);
				edge[i].push_back(j);
				++ind[j];
				++bind[i];
			}
		}
	}
	int src = 1; d = 1; sign = -1;
	for (i = 1; i <= n; ++i) {
		if (s[i] == 0) perm_sort(i,src,s,ind,edge,back);
	}
	d = -1; src = n;
	//for (i = n, src = n; i > 0; --i) {
	for(i=1;i<=n;++i){
		if (l[i] == 0) perm_sort(i, src, l, bind, back, 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 (stderr)

zagonetka.cpp: In function 'void qry(int, int)':
zagonetka.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < loc.size(); ++i) {
                  ~~^~~~~~~~~~~~
zagonetka.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < loc.size(); ++j) {
                   ~~^~~~~~~~~~~~
zagonetka.cpp:105: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:117: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:118: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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 51