Submission #398966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
398966	2021-05-04T23:20:32 Z	AmineWeslati	The Collection Game (BOI21_swaps)	C++14	27 / 100	435 ms	12416 KB

swaps

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

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
typedef pair<int,int> pi;
#define fi first
#define se second
typedef vector<pi>vpi;
#define eb emplace_back

#define FOR(i,a,b) for(int i=a; i<b; i++)

void ckmin(int &x, int y){x=min(x,y);}

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}

//------------------------------------------------------------------//

const int MX=505;
vi adj[MX],order,vis(MX,0);

void dfs(int u){
	vis[u]=1;
	for(int v: adj[u]) if(!vis[v]){
		dfs(v);
	}
	order.pb(u);
}

void solve(int N, int V) {
	set<pi>s;
	FOR(i,1,N+1) FOR(j,i+1,N+1) s.insert({i,j});
	
	while(sz(s)){
		vi vis(N+1,0);
		vpi vec;
		for(auto it: s){
			int u=it.fi,v=it.se;
			if(!vis[u] && !vis[v]){
				vec.eb(it);
				vis[u]=vis[v]=1;
			}
		}

		for(auto x: vec){
			schedule(x.fi,x.se);
			s.erase(x);
		}

		vi vv=visit();

		FOR(i,0,sz(vec)){
			int u=vec[i].fi,v=vec[i].se;
			if(vv[i]) swap(u,v);
			adj[u].pb(v);
		}
	}

	FOR(i,1,N+1) if(!vis[i]) dfs(i);
	answer(order);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	10 ms	584 KB	Correct
3	Correct	63 ms	1796 KB	Correct
4	Correct	396 ms	6228 KB	Correct
5	Correct	406 ms	6272 KB	Correct
6	Correct	415 ms	6176 KB	Correct
7	Correct	393 ms	6428 KB	Correct
8	Correct	403 ms	6288 KB	Correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	8 ms	456 KB	Correct
3	Correct	63 ms	1800 KB	Correct
4	Correct	394 ms	6212 KB	Correct
5	Correct	383 ms	6176 KB	Correct
6	Correct	395 ms	6412 KB	Correct
7	Correct	396 ms	6272 KB	Correct
8	Correct	395 ms	6392 KB	Correct
9	Correct	390 ms	6360 KB	Correct
10	Correct	402 ms	6164 KB	Correct
11	Correct	395 ms	6280 KB	Correct
12	Correct	391 ms	6292 KB	Correct
13	Correct	387 ms	6164 KB	Correct

Subtask #3
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	10 ms	584 KB	Correct

Subtask #4
0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	10 ms	584 KB	Correct
3	Incorrect	1 ms	200 KB	Not correct
4	Halted	0 ms	0 KB	-

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	8 ms	584 KB	Correct
3	Correct	65 ms	1736 KB	Correct
4	Correct	425 ms	6344 KB	Correct

Subtask #6
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	8 ms	584 KB	Correct
3	Correct	65 ms	1736 KB	Correct
4	Correct	425 ms	6344 KB	Correct
5	Correct	1 ms	200 KB	Correct
6	Correct	8 ms	456 KB	Correct
7	Correct	64 ms	1736 KB	Correct
8	Correct	392 ms	6212 KB	Correct
9	Correct	394 ms	6164 KB	Correct
10	Correct	404 ms	6272 KB	Correct
11	Correct	435 ms	6212 KB	Correct
12	Correct	396 ms	6164 KB	Correct
13	Incorrect	1 ms	200 KB	Not correct
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	8 ms	456 KB	Correct
3	Correct	64 ms	1796 KB	Correct
4	Correct	397 ms	6280 KB	Correct
5	Runtime error	393 ms	12252 KB	Execution killed with signal 11

Subtask #8
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	8 ms	456 KB	Correct
3	Correct	64 ms	1796 KB	Correct
4	Correct	397 ms	6280 KB	Correct
5	Runtime error	393 ms	12252 KB	Execution killed with signal 11

Subtask #9
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	9 ms	584 KB	Correct
3	Correct	62 ms	1772 KB	Correct
4	Correct	393 ms	6212 KB	Correct
5	Runtime error	399 ms	12416 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #10
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	9 ms	584 KB	Correct
3	Correct	62 ms	1772 KB	Correct
4	Correct	393 ms	6212 KB	Correct
5	Runtime error	399 ms	12416 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #11
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	9 ms	584 KB	Correct
3	Correct	63 ms	1816 KB	Correct
4	Correct	399 ms	6200 KB	Correct
5	Runtime error	408 ms	12332 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #12
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Correct
2	Correct	9 ms	584 KB	Correct
3	Correct	63 ms	1816 KB	Correct
4	Correct	399 ms	6200 KB	Correct
5	Runtime error	408 ms	12332 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Submission #398966

Compilation message