Submission #38059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38059	2017-12-31T12:02:38 Z	14kg	Collider (IZhO11_collider)	C++11	100 / 100	89 ms	13812 KB

collider

#include <stdio.h>
#define N 1000005

struct DB {
	char data;
	int left, right;
} in[N];
int n, nn, hash[1002];
char temp[N];

int search(int x) {
	int w = hash[x / 1000], k = (x / 1000) * 1000;

	while (k < x) k++, w = in[w].right;
	return w;
}
int main() {
	int m, x, y;
	char s;

	scanf("%d %d %s ", &n, &m, temp + 1), nn = n / 1000;
	for (int i = 1; i <= nn; i++) hash[i] = i * 1000;

	in[0].right = 1, in[n + 1].left = n;
	for (int i = 1; i <= n; i++) {
		in[i].data = temp[i], in[i].left = i - 1, in[i].right = i + 1;
	}

	while (m--) {
		scanf("%c ", &s);
		if (s == 'q') {
			scanf("%d ", &x);
			printf("%c\n", in[search(x)].data);
		}
		else {
			scanf("%d %d ", &x, &y);
			int wx = search(x), wy = search(y);

			if (x < y) {
				for (int i = (x - 1) / 1000 + 1; i <= y / 1000; i++)
					if (i * 1000 == y) hash[i] = wx;
					else hash[i] = in[hash[i]].right;

				in[in[wx].left].right = in[wx].right;
				in[in[wx].right].left = in[wx].left;
				in[in[wy].right].left = wx;
				in[wx].left = wy;
				in[wx].right = in[wy].right;
				in[wy].right = wx;
			}
			if (y < x) {
				for (int i = (y - 1) / 1000 + 1; i <= x / 1000; i++)
					if (i * 1000 == y) hash[i] = wx;
					else hash[i] = in[hash[i]].left;

				in[in[wx].left].right = in[wx].right;
				in[in[wx].right].left = in[wx].left;
				in[in[wy].left].right = wx;
				in[wx].left = in[wy].left;
				in[wx].right = wy;
				in[wy].left = wx;
			}
		}
	}
}

Compilation message

collider.cpp: In function 'int main()':
collider.cpp:21:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %s ", &n, &m, temp + 1), nn = n / 1000;
                                                     ^
collider.cpp:30:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c ", &s);
                   ^
collider.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d ", &x);
                    ^
collider.cpp:36:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d ", &x, &y);
                           ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	13812 KB	Output is correct
2	Correct	26 ms	13812 KB	Output is correct
3	Correct	16 ms	13812 KB	Output is correct
4	Correct	23 ms	13812 KB	Output is correct
5	Correct	49 ms	13812 KB	Output is correct
6	Correct	53 ms	13812 KB	Output is correct
7	Correct	66 ms	13812 KB	Output is correct
8	Correct	23 ms	13812 KB	Output is correct
9	Correct	89 ms	13812 KB	Output is correct
10	Correct	59 ms	13812 KB	Output is correct