oj.uz

Submission #1048519

# Submission time Handle Problem Language Result Execution time Memory
1048519 2024-08-08T08:05:43 Z 박영우(#11091) Make them Meet (EGOI24_makethemmeet) C++17
13 / 100
 19 ms 51548 KB 
//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXQ 101010
#define INF 1'000'000'100'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
#ifdef LOCAL
#define DEBUG(a) cout<<a
#define TEST true
#else
#define DEBUG(...) 1234
#define TEST false
#endif
vector<int> adj[MAX];
vector<vector<int>> ansv;
int chk[MAX];
int A[MAX];
int inv[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0); int N, M;
	cin >> N >> M;
	assert(M == N * (N - 1) / 2);
	int d, i;
	for (i = 0; i < N; i++) A[i] = inv[i] = i;
	auto f = [&](int a, int b) {
		int i = inv[a];
		int j = inv[b];
		swap(inv[a], inv[b]);
		swap(A[i], A[j]);
	}; //swap by value
	for (d = 1; d < N; d++) {
		vector<int> v(N, -1);
		int cnt = 0;
		for (i = 0; i < N; i++) chk[i] = 0;
		for (i = 0; i < N; i++) if (i + d < N) chk[i + d] = chk[i] ^ 1;
		for (i = 0; i < N; i++) if (i + d < N && !chk[i + d]) {
			v[inv[i]] = v[inv[i + d]] = ++cnt;
			f(i, i + d);
		}
		for (i = 0; i < N; i++) if (v[i] < 0) v[i] = ++cnt;
		ansv.push_back(v);

		v = vector<int>(N, -1);
		cnt = 0;
		for (i = 0; i < N; i++) chk[i] = 1;
		for (i = 0; i < N; i++) if (i + d < N) chk[i + d] = chk[i] ^ 1;
		for (i = 0; i < N; i++) if (i + d < N && !chk[i + d]) {
			v[inv[i]] = v[inv[i + d]] = ++cnt;
			f(i, i + d);
		}
		for (i = 0; i < N; i++) if (v[i] < 0) v[i] = ++cnt;
		ansv.push_back(v);
	}
	cout << ansv.size() << ln;
	for (auto& v : ansv) {
		for (auto x : v) cout << x << bb;
		cout << ln;
	}
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Runtime error 17 ms 51548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29532 KB Output is correct
2 Correct 4 ms 29532 KB Output is correct
3 Correct 4 ms 29532 KB Output is correct
4 Correct 4 ms 29532 KB Output is correct
5 Correct 3 ms 29652 KB Output is correct
6 Correct 4 ms 29532 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Correct 4 ms 29532 KB Output is correct
9 Correct 5 ms 30040 KB Output is correct

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29532 KB Output is correct
2 Runtime error 19 ms 51408 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Runtime error 17 ms 51548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Runtime error 17 ms 51548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -