QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731176#5380. Bell RingingTheZoneAC ✓309ms34820kbC++236.6kb2024-11-10 00:22:042024-11-10 00:22:05

Judging History

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

  • [2024-11-10 00:22:05]
  • 评测
  • 测评结果：AC
  • 用时：309ms
  • 内存：34820kb
查看
  • [2024-11-10 00:22:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

VI g[74747];
VI ans;
int deg[74747];
bool used[74747];
int dg;
int md = 6;

void dfs(int v)
{
	used[v] = 1;
	ans.PB(v);
	vector<PII> a;
	for (auto to : g[v])
	{
		if (!used[to])
		{
			deg[to]--;
			a.PB({deg[to] + (rand() % md), to});
		}
	}
	sort(ALL(a));
	if (SZ(a))
		dfs(a[0].second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	srand(40);
	
	int n;
	cin >> n;
	
	if (n == 8) md = 12;

	VI v(n);
	iota(ALL(v), 1);
	vector<VI> p;
	map<VI, int> mapka;
	do
	{
		mapka[v] = SZ(p);
		p.PB(v);
	}while(next_permutation(ALL(v)));
	FOR(i, 0, SZ(p))
	{
		FOR (mask, 1, 1 << (n - 1))
		{
			bool bad = false;
			FOR (j, 0, n - 2)
				if (((mask >> j) & 3) == 3)
					bad = true;
			if (bad) continue;
			VI p2 = p[i];
			FOR(j, 0, n - 1)
				if (mask & (1 << j))
					swap(p2[j], p2[j + 1]);
	
			int j = mapka[p2];
			g[i].PB(j);
			deg[i]++;
		}
	}
	dg = deg[0];
	int mx = 0;
	do
	{
		ans.clear();
		FOR(i, 0, SZ(p))
		{
			deg[i] = dg;
			used[i] = false;
			
		}
		dfs(0);
		mx = max(mx, SZ(ans));
	} while (SZ(ans) != SZ(p));
	FOR(i, 0, SZ(ans))
	{
		FOR(j, 0, n)
		{
			cout << p[ans[i]][j] << ' ';
		}
		cout << '\n';
	}
	cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	
	return 0;
}


/*#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

VI g[74747];
VI ans;
int deg[74747];
bool used[74747];
int dg;
int md = 6;

void dfs(int v)
{
	used[v] = 1;
	ans.PB(v);
	vector<PII> a;
	for (auto to : g[v])
	{
		if (!used[to])
		{
			deg[to]--;
			a.PB({deg[to] + (rand() % md), to});
		}
	}
	sort(ALL(a));
	if (SZ(a))
		dfs(a[0].second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	srand(40);
	
	int n;
	cin >> n;
	
	if (n == 8) md = 12;

	VI v(n);
	iota(ALL(v), 1);
	vector<VI> p;
	map<VI, int> mapka;
	do
	{
		mapka[v] = SZ(p);
		p.PB(v);
	}while(next_permutation(ALL(v)));
	FOR(i, 0, SZ(p))
	{
		FOR (mask, 1, 1 << (n - 1))
		{
			bool bad = false;
			FOR (j, 0, n - 2)
				if (((mask >> j) & 3) == 3)
					bad = true;
			if (bad) continue;
			VI p2 = p[i];
			FOR(j, 0, n - 1)
				if (mask & (1 << j))
					swap(p2[j], p2[j + 1]);
	
			int j = mapka[p2];
			g[i].PB(j);
			deg[i]++;
		}
	}
	dg = deg[0];
	int mx = 0;
	do
	{
		ans.clear();
		FOR(i, 0, SZ(p))
		{
			deg[i] = dg;
			used[i] = false;
			
		}
		dfs(0);
		mx = max(mx, SZ(ans));
	} while (SZ(ans) != SZ(p));
	FOR(i, 0, SZ(ans))
	{
		FOR(j, 0, n)
		{
			cout << p[ans[i]][j] << ' ';
		}
		cout << '\n';
	}
	cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	
	return 0;
}


#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

VI g[74747];
VI ans;
int deg[74747];
bool used[74747];
int dg;
int md = 6;

void dfs(int v)
{
	used[v] = 1;
	ans.PB(v);
	vector<PII> a;
	for (auto to : g[v])
	{
		if (!used[to])
		{
			deg[to]--;
			a.PB({deg[to] + (rand() % md), to});
		}
	}
	sort(ALL(a));
	if (SZ(a))
		dfs(a[0].second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	srand(40);
	
	int n;
	cin >> n;
	
	if (n == 8) md = 12;

	VI v(n);
	iota(ALL(v), 1);
	vector<VI> p;
	map<VI, int> mapka;
	do
	{
		mapka[v] = SZ(p);
		p.PB(v);
	}while(next_permutation(ALL(v)));
	FOR(i, 0, SZ(p))
	{
		FOR (mask, 1, 1 << (n - 1))
		{
			bool bad = false;
			FOR (j, 0, n - 2)
				if (((mask >> j) & 3) == 3)
					bad = true;
			if (bad) continue;
			VI p2 = p[i];
			FOR(j, 0, n - 1)
				if (mask & (1 << j))
					swap(p2[j], p2[j + 1]);
	
			int j = mapka[p2];
			g[i].PB(j);
			deg[i]++;
		}
	}
	dg = deg[0];
	int mx = 0;
	do
	{
		ans.clear();
		FOR(i, 0, SZ(p))
		{
			deg[i] = dg;
			used[i] = false;
			
		}
		dfs(0);
		mx = max(mx, SZ(ans));
	} while (SZ(ans) != SZ(p));
	FOR(i, 0, SZ(ans))
	{
		FOR(j, 0, n)
		{
			cout << p[ans[i]][j] << ' ';
		}
		cout << '\n';
	}
	cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	
	return 0;
}


#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

VI g[74747];
VI ans;
int deg[74747];
bool used[74747];
int dg;
int md = 6;

void dfs(int v)
{
	used[v] = 1;
	ans.PB(v);
	vector<PII> a;
	for (auto to : g[v])
	{
		if (!used[to])
		{
			deg[to]--;
			a.PB({deg[to] + (rand() % md), to});
		}
	}
	sort(ALL(a));
	if (SZ(a))
		dfs(a[0].second);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	srand(40);
	
	int n;
	cin >> n;
	
	if (n == 8) md = 12;

	VI v(n);
	iota(ALL(v), 1);
	vector<VI> p;
	map<VI, int> mapka;
	do
	{
		mapka[v] = SZ(p);
		p.PB(v);
	}while(next_permutation(ALL(v)));
	FOR(i, 0, SZ(p))
	{
		FOR (mask, 1, 1 << (n - 1))
		{
			bool bad = false;
			FOR (j, 0, n - 2)
				if (((mask >> j) & 3) == 3)
					bad = true;
			if (bad) continue;
			VI p2 = p[i];
			FOR(j, 0, n - 1)
				if (mask & (1 << j))
					swap(p2[j], p2[j + 1]);
	
			int j = mapka[p2];
			g[i].PB(j);
			deg[i]++;
		}
	}
	dg = deg[0];
	int mx = 0;
	do
	{
		ans.clear();
		FOR(i, 0, SZ(p))
		{
			deg[i] = dg;
			used[i] = false;
			
		}
		dfs(0);
		mx = max(mx, SZ(ans));
	} while (SZ(ans) != SZ(p));
	FOR(i, 0, SZ(ans))
	{
		FOR(j, 0, n)
		{
			cout << p[ans[i]][j] << ' ';
		}
		cout << '\n';
	}
	cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
	
	return 0;
}


*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3832kb

input:

2

output:

1 2 
2 1

result:

ok Thank you for your great code. It was fantastic.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

3

output:

1 2 3 
1 3 2 
3 1 2 
3 2 1 
2 3 1 
2 1 3

result:

ok Thank you for your great code. It was fantastic.

Test #3:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

1

output:

1

result:

ok Thank you for your great code. It was fantastic.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

4

output:

1 2 3 4 
1 2 4 3 
1 4 2 3 
1 4 3 2 
4 1 2 3 
4 1 3 2 
4 3 1 2 
3 4 1 2 
3 1 4 2 
1 3 4 2 
1 3 2 4 
3 1 2 4 
3 2 1 4 
2 3 4 1 
2 4 3 1 
4 2 1 3 
2 4 1 3 
4 2 3 1 
4 3 2 1 
3 4 2 1 
3 2 4 1 
2 3 1 4 
2 1 3 4 
2 1 4 3

result:

ok Thank you for your great code. It was fantastic.

Test #5:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

5

output:

1 2 3 4 5 
1 3 2 4 5 
1 3 4 2 5 
1 4 3 2 5 
1 4 3 5 2 
4 1 3 5 2 
4 1 5 3 2 
1 4 5 3 2 
1 5 4 3 2 
1 4 5 2 3 
4 1 5 2 3 
4 1 2 5 3 
1 4 2 3 5 
4 1 3 2 5 
4 3 1 5 2 
4 3 1 2 5 
3 4 1 2 5 
3 1 4 2 5 
1 3 4 5 2 
1 3 5 4 2 
3 1 4 5 2 
3 4 1 5 2 
3 4 5 1 2 
4 3 5 1 2 
4 3 5 2 1 
4 5 3 1 2 
5 4 1 3 2 
5 1...

result:

ok Thank you for your great code. It was fantastic.

Test #6:

score: 0
Accepted
time: 5ms
memory: 4280kb

input:

6

output:

1 2 3 4 5 6 
1 3 2 4 6 5 
1 2 3 4 6 5 
1 2 4 3 6 5 
1 2 4 3 5 6 
2 1 3 4 6 5 
1 2 3 6 4 5 
1 2 6 3 4 5 
1 6 2 3 4 5 
6 1 2 3 4 5 
6 1 3 2 4 5 
1 6 2 3 5 4 
1 2 6 3 5 4 
1 6 2 5 3 4 
6 1 2 5 3 4 
6 1 2 3 5 4 
1 6 3 2 5 4 
1 6 3 2 4 5 
6 1 3 2 5 4 
6 3 1 2 5 4 
6 3 2 1 5 4 
6 3 1 2 4 5 
6 1 3 4 2 5 
6...

result:

ok Thank you for your great code. It was fantastic.

Test #7:

score: 0
Accepted
time: 44ms
memory: 6740kb

input:

7

output:

1 2 3 4 5 6 7 
1 2 3 4 5 7 6 
2 1 3 5 4 7 6 
2 1 3 4 5 6 7 
1 2 3 5 4 6 7 
2 1 3 4 5 7 6 
1 2 4 3 5 7 6 
2 1 4 3 5 7 6 
1 2 4 3 5 6 7 
2 1 4 3 5 6 7 
2 1 4 5 3 6 7 
1 2 4 5 3 7 6 
2 1 4 5 3 7 6 
1 2 4 5 3 6 7 
1 4 2 5 3 7 6 
1 4 2 3 5 6 7 
1 4 2 5 3 6 7 
4 1 2 3 5 6 7 
1 4 2 3 5 7 6 
4 1 2 5 3 7 6 
...

result:

ok Thank you for your great code. It was fantastic.

Test #8:

score: 0
Accepted
time: 309ms
memory: 34820kb

input:

8

output:

1 2 3 4 5 6 7 8 
1 2 3 5 4 6 8 7 
1 2 3 4 5 6 8 7 
1 2 3 4 5 8 6 7 
1 3 2 4 5 6 8 7 
1 3 2 5 4 6 7 8 
1 3 2 4 5 6 7 8 
1 3 2 5 4 7 6 8 
1 2 3 5 4 6 7 8 
2 1 3 5 4 6 7 8 
1 2 3 5 4 7 6 8 
1 2 3 4 5 7 6 8 
1 2 3 5 4 7 8 6 
1 2 3 4 5 7 8 6 
1 3 2 4 5 7 6 8 
1 3 2 5 4 7 8 6 
1 3 2 4 5 7 8 6 
1 2 3 4 5 8...

result:

ok Thank you for your great code. It was fantastic.
English 繁體中文 简体中文

Server Time: 2024-11-30 06:45:33 | OpenSource Project