QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429239#7278. Brought Down the Grading Server?ItamarN0 32ms15148kbC++142.5kb2024-06-02 05:57:352024-06-02 05:57:35

Judging History

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

  • [2024-06-02 05:57:35]
  • 评测
  • 测评结果:0
  • 用时:32ms
  • 内存:15148kb
  • [2024-06-02 05:57:35]
  • 提交

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 tr = 1; tr <= t; 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] << ' ';
		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: 3560kb

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: 3600kb

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: 32ms
memory: 15148kb

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 
26...

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: 3556kb

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: 2ms
memory: 4220kb

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 471 1051 
786 1776 705 2269 
1674 1622 755 1277 
590 1217 1378 603 
1658 967 239 1920 
1589 78 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 
1779 2254 521 2334 
1508 19...

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%