제출 #1350275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1350275		NikoBaotic	Tenis (COI19_tenis)	C++20	51 / 100	509 ms	9336 KiB

tenis

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second

const int N = 1e5 + 10;
const int M = 3;
int K = 130;

int n, q;
int p[M][N];
int poz[M][N];
int qu[N][4];
int sav[N][M];
bool vaz[N];
bool h[N];
int dp[M][N][M];
vector<int> v[M];

int main() {
	scanf("%d%d", &n, &q);

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &(p[i][j]));
			poz[i][p[i][j]] = j;
		}
	}

	int up = 0;

	for (int i = 0; i < q; i++) {
		scanf("%d", &(qu[i][0]));

		if (qu[i][0] == 1) {
			scanf("%d", &(qu[i][1]));
		} else {
			scanf("%d%d%d", &(qu[i][1]), &(qu[i][2]), &(qu[i][3]));
			qu[i][1]--;
			up++;
		}
	}

	if (up > n / 2) {
		K = 350;
	}

	int s = 0;
	while (s < q) {
		int e = s;
		int cnt = 0;

		while (e < q and cnt < K) {
			if (qu[e][1] == 2) cnt++;
			e++;
		}

		memset(vaz, 0, sizeof vaz);
		for (int i = s; i < e; i++) {
			if (qu[i][0] == 1) continue;
			vaz[qu[i][2]] = 1;
			vaz[qu[i][3]] = 1;
		}

		for (int i = 0; i < M; i++) {
			v[i].clear();

			for (int j = n - 1; j >= 0; j--) {
				if (vaz[p[i][j]]) v[i].pb(j);
			}
		}

		for (int t = 0; t < M; t++) {
			memset(h, 0, sizeof h);
			int cur[3] = {n, n, n};
			int tar[3] = {n, n, n};

			for (int i = n - 1; i >= 0; i--) {
				tar[t] = min(tar[t], i);

				while (1) {
					bool ch = 0;

					for (int j = 0; j < M; j++) {
						while (tar[j] < cur[j]) {
							cur[j]--;

							if (vaz[p[j][cur[j]]] + h[p[j][cur[j]]] == 0) {
								h[p[j][cur[j]]] = 1;
								for (int l = 0; l < M; l++) {
									tar[l] = min(tar[l], poz[l][p[j][cur[j]]]);
								}
							}
						
							ch = 1;
						}
					}


					if (!ch) break;
				}

				for (int j = 0; j < M; j++) {
					dp[t][i][j] = cur[j];
				}
			}
		}
		
		for (int i = 1; i <= n; i++) {
			if (!vaz[i]) continue;
			for (int l = 0; l < M; l++) {
				sav[i][l] = n;

				for (int j = 0; j < M; j++) {
					sav[i][l] = min(sav[i][l], dp[j][poz[j][i]][l]);
				}
			}
		}

		for (int i = s; i < e; i++) {
			if (qu[i][0] == 1) {
				int cur[3];

				for (int j = 0; j < M; j++) {
					cur[j] = dp[j][poz[j][qu[i][1]]][j];
				}

				int tr[3] = {0, 0, 0};

				while (1) {
					bool ch = 0;

					for (int j = 0; j < M; j++) {
						while (tr[j] < sz(v[j]) and v[j][tr[j]] >= cur[j]) {
							for (int l = 0; l < M; l++) {
								cur[l] = min(cur[l], sav[p[j][v[j][tr[j]]]][l]);
							}

							ch = 1;
							tr[j]++;
						}
					}

					if (!ch) break;
				}

				if (cur[0]) {
					printf("NE\n");
				} else {
					printf("DA\n");
				}
			} else {
				int t = qu[i][1];
				int v1 = qu[i][2];
				int v2 = qu[i][3];

				swap(p[t][poz[t][v1]], p[t][poz[t][v2]]);
				swap(poz[t][v1], poz[t][v2]);

				for (int l = 0; l < M; l++) {
					sav[v1][l] = n;
					sav[v2][l] = n;

					for (int j = 0; j < M; j++) {
						sav[v1][l] = min(sav[v1][l], dp[j][poz[j][v1]][l]);
						sav[v2][l] = min(sav[v2][l], dp[j][poz[j][v2]][l]);
					}
				}
			}
		}
	
		s = e;
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tenis.cpp: In function 'int main()':
tenis.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d%d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:33:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |                         scanf("%d", &(p[i][j]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
tenis.cpp:41:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |                 scanf("%d", &(qu[i][0]));
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
tenis.cpp:44:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |                         scanf("%d", &(qu[i][1]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~
tenis.cpp:46:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |                         scanf("%d%d%d", &(qu[i][1]), &(qu[i][2]), &(qu[i][3]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 49