oj.uz

Submission #136348

# Submission time Handle Problem Language Result Execution time Memory
136348 2019-07-25T07:25:41 Z 이온조(#3259) Queue (CEOI06_queue) C++14
0 / 100
 539 ms 20084 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9;
vector<int> S;
int A[50009], B[50009];
map<int, int> L, R, P, O;

inline bool chk(int x) { return x == *lower_bound(S.begin(), S.end(), x); }

inline int geti(vector<int> &T, int x) { return lower_bound(T.begin(), T.end(), x) - T.begin(); }

void showpos() {
	printf("showing position\n");
	for(auto& it: P) printf("position of %d: %d\n", it.first, it.second);
	puts("\n\n");
}

int main() {
	vector<int> PR, NW;
	int N; scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d%d", &A[i], &B[i]);
		S.push_back(A[i]);
		S.push_back(B[i]);
	}
	S.push_back(0); S.push_back(INF);
	sort(S.begin(), S.end()); S.resize(unique(S.begin(), S.end()) - S.begin());
	int K = S.size() - 2;
	R[0] = S[1]; L[INF] = S[K];
	for(int i=1; i<=K; i++) {
		R[S[i]] = S[i+1], L[S[i]] = S[i-1], P[S[i]] = S[i], O[S[i]] = i;
		PR.push_back(S[i]);
	}
	showpos();
	for(int i=1; i<=N; i++) {
		int l = L[A[i]], r = R[A[i]];
		R[l] = r; L[r] = l;
		R[A[i]] = B[i]; L[A[i]] = L[B[i]];
		R[L[B[i]]] = A[i]; L[B[i]] = A[i];
		P[A[i]] = P[B[i]];

	}
	int now = R[0], cnt = 1;
	while(now != INF) {
		printf("now: %d\n", now);
		printf("position: %d\n\n", P[now]);
		NW.push_back(P[now]);
		P[now] += cnt - O[now];
		printf("position: %d\n\n", P[now]);
		now = R[now];
		++cnt;
	}
	int Q; scanf("%d",&Q);
	while(Q--) {
		char t; int x; scanf(" %c%d",&t,&x);
		if(t == 'P') {
			if(chk(x)) printf("%d\n", P[x]);
			else printf("%d\n", x + geti(NW, x) - geti(PR, x));
		}
		if(t == 'L') {
			printf("%d\n", 123456789);
		}
	}
	return 0;
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
queue.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
queue.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d",&Q);
         ~~~~~^~~~~~~~~
queue.cpp:56:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char t; int x; scanf(" %c%d",&t,&x);
                  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Expected integer, but "showing" found
2 Incorrect 2 ms 256 KB Expected integer, but "showing" found
3 Incorrect 3 ms 376 KB Expected integer, but "showing" found
4 Incorrect 5 ms 504 KB Expected integer, but "showing" found
5 Incorrect 32 ms 1444 KB Expected integer, but "showing" found
6 Incorrect 56 ms 2552 KB Expected integer, but "showing" found
7 Incorrect 78 ms 3932 KB Expected integer, but "showing" found
8 Incorrect 96 ms 5884 KB Expected integer, but "showing" found
9 Incorrect 118 ms 6216 KB Expected integer, but "showing" found
10 Incorrect 133 ms 6776 KB Expected integer, but "showing" found
11 Incorrect 400 ms 13800 KB Expected integer, but "showing" found
12 Incorrect 371 ms 12912 KB Expected integer, but "showing" found
13 Incorrect 431 ms 13784 KB Expected integer, but "showing" found
14 Incorrect 381 ms 13936 KB Expected integer, but "showing" found
15 Incorrect 387 ms 13972 KB Expected integer, but "showing" found
16 Incorrect 422 ms 13744 KB Expected integer, but "showing" found
17 Incorrect 29 ms 1012 KB Expected integer, but "showing" found
18 Incorrect 57 ms 1624 KB Expected integer, but "showing" found
19 Incorrect 89 ms 2056 KB Expected integer, but "showing" found
20 Incorrect 152 ms 3056 KB Expected integer, but "showing" found
21 Incorrect 334 ms 14328 KB Expected integer, but "showing" found
22 Incorrect 425 ms 17376 KB Expected integer, but "showing" found
23 Incorrect 530 ms 19940 KB Expected integer, but "showing" found
24 Incorrect 539 ms 20084 KB Expected integer, but "showing" found
25 Incorrect 525 ms 19952 KB Expected integer, but "showing" found