QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429244#7278. Brought Down the Grading Server?ItamarN0 125ms15184kbC++142.6kb2024-06-02 06:05:432024-06-02 06:05:44

Judging History

你现在查看的是最新测评结果

  • [2024-06-02 06:05:44]
  • 评测
  • 测评结果:0
  • 用时:125ms
  • 内存:15184kb
  • [2024-06-02 06:05:43]
  • 提交

answer

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>

int n, s, t;
vector<vi> v;

void solve(vector<pi>&ed) {
	int m = ed.size();
	vector<vector<pi>> fr(t+2);
	vi it(t + 2);
	for (int i = 0; i < m; i++) {
		fr[ed[i].x].push_back({ ed[i].y,i });
		fr[ed[i].y].push_back({ ed[i].x,i });
	}
	for (int i = 1; i <= t; i++) {
		if ((fr[i].size()) % 2) {
			fr[i].push_back({ t + 1,ed.size()});
			fr[t + 1].push_back({ i,ed.size() });
			ed.push_back({ i,t + 1 });
		}
	}
	vi vis(ed.size());
	for (int k = 0; k < 1000; k++) {
		for (int tr = 1; tr <= t+1; tr++) {
			int i = tr;
			while (it[i] < fr[i].size()) {
				if (vis[fr[i][it[i]].y])it[i]++;
				else {
					int e = fr[i][it[i]].y;
					vis[e] = 1;
					if (ed[e].x != i) {
						swap(ed[e].x, ed[e].y);
					}
					i = fr[i][it[i]].x;
					it[i]++;
				}
			}
		}
	}

}

void rec(int l, int r) {
	if (l == r)return;
	int mid = (l + r) / 2;
	vector<pi> ed;
	for (int j = l; j <= mid; j++) {
		for (int i = 0; i < n; i++) {
			ed.push_back({ v[i][j],v[i][2 * mid - j+1] });
		}
	}
	solve(ed);
	for (int j = l; j <= mid; j++) {
		for (int i = 0; i < n; i++) {
			if (v[i][j] != ed[(j-l) * n + i].x) {
				swap(v[i][j], v[i][2 * mid - j+1]);
			}
		}
	}
	rec(l, mid);
	rec(mid+1, r);
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> s >> t;
	v.resize(n, vi(s));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < s; j++) {
			cin >> v[i][j];
		}
	}
	rec(0, s - 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < s; j++) {
			cout << v[i][j];
			if (j < s - 1)cout << ' ';
		}
		if(i<n-1)cout << "\n";
	}
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 3592kb

input:

3 2 3
1 2
2 3
2 3

output:

1 2
2 3
3 2

result:

ok 

Test #2:

score: -10
Wrong Answer
time: 0ms
memory: 3520kb

input:

20 2 20
18 2
12 5
20 9
4 2
17 4
7 15
9 2
5 5
13 15
19 5
3 5
10 19
8 5
7 10
9 11
3 16
7 18
9 5
3 8
18 4

output:

2 18
12 5
20 9
4 2
4 17
7 15
2 9
5 5
13 15
5 19
3 5
19 10
5 8
7 10
9 11
3 16
18 7
5 9
8 3
18 4

result:

wrong answer 

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 125ms
memory: 15184kb

input:

100000 2 100000
70318 14894
32116 90327
63866 29061
53683 63612
70370 78264
42647 76881
39251 31741
61186 66491
57686 65819
53278 59145
71962 26052
81040 55279
50859 51310
46800 24546
85013 91165
61530 21890
84003 29099
33573 86182
49212 10639
91851 97312
57682 14067
5243 69674
99007 62508
26290 555...

output:

70318 14894
32116 90327
63866 29061
53683 63612
70370 78264
42647 76881
31741 39251
61186 66491
57686 65819
53278 59145
71962 26052
81040 55279
50859 51310
24546 46800
85013 91165
61530 21890
84003 29099
33573 86182
10639 49212
91851 97312
14067 57682
5243 69674
99007 62508
26290 55524
15519 43794
5...

result:

wrong answer 

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #56:

score: 15
Accepted
time: 0ms
memory: 3596kb

input:

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

output:

2 2 2 3
2 3 3 2
3 2 2 2

result:

ok 

Test #57:

score: -15
Wrong Answer
time: 9ms
memory: 4016kb

input:

2450 4 2450
540 475 1156 2334
2421 2439 1328 750
471 1051 2007 1792
1776 786 705 2269
1277 755 1674 1622
590 1378 1217 603
967 239 1658 1920
857 2307 1589 78
2172 861 2322 1634
2077 2021 1381 2179
1126 345 1547 2126
994 1214 1477 412
1857 2085 831 978
281 1844 2406 2174
521 2334 2254 1779
1508 905 1...

output:

540 475 1156 2334
1328 2421 750 2439
1792 2007 1051 471
786 1776 705 2269
1674 1622 755 1277
590 1217 1378 603
967 1658 239 1920
78 1589 857 2307
2322 2172 861 1634
2077 2021 1381 2179
1126 1547 345 2126
1214 994 412 1477
1857 2085 831 978
281 2406 1844 2174
2254 1779 521 2334
1508 1903 284 905
345 ...

result:

wrong answer 

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #2:

0%

Subtask #9:

score: 0
Skipped

Dependency #3:

0%

Subtask #10:

score: 0
Skipped

Dependency #1:

0%