Submission #1077221

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077221	2024-08-27T03:22:20 Z	LCJLY	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	628 ms	600 KB

arranging_tickets

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef array<int,4>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

void solve(){ 	
	int n,m;
	cin >> n >> m;
	pii arr[m];
	int temp,temp2,temp3;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2 >> temp3;
		temp--;
		temp2--;
		if(temp>temp2) swap(temp,temp2);
		arr[x]={temp,temp2};
	}
	
	int mini=1e15;
	for(int x=0;x<(1<<m);x++){
		int dp[n+5];
		memset(dp,0,sizeof(dp));
		for(int y=0;y<m;y++){
			if(x&(1<<y)){
				int cur=arr[y].second;
				while(cur!=arr[y].first){
					dp[cur]++;
					cur=(cur+1)%n;
				}
			}
			else{
				int cur=arr[y].first;
				while(cur!=arr[y].second){
					dp[cur]++;
					cur=(cur+1)%n;
				}
			}
		}
		int maxi=0;
		for(int x=0;x<n;x++){
			maxi=max(maxi,dp[x]);
		}
		mini=min(mini,maxi);
	}
	cout << mini;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	//freopen("hand.txt","r",stdin);
	while(t--){
		solve();
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	344 KB	Output is correct
2	Correct	528 ms	348 KB	Output is correct
3	Correct	541 ms	596 KB	Output is correct
4	Correct	540 ms	448 KB	Output is correct
5	Correct	538 ms	344 KB	Output is correct
6	Correct	529 ms	348 KB	Output is correct
7	Correct	531 ms	344 KB	Output is correct
8	Correct	533 ms	440 KB	Output is correct
9	Correct	528 ms	436 KB	Output is correct
10	Correct	528 ms	344 KB	Output is correct
11	Correct	528 ms	436 KB	Output is correct
12	Correct	538 ms	600 KB	Output is correct
13	Correct	526 ms	432 KB	Output is correct
14	Correct	530 ms	440 KB	Output is correct
15	Correct	536 ms	344 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	344 KB	Output is correct
2	Correct	528 ms	348 KB	Output is correct
3	Correct	541 ms	596 KB	Output is correct
4	Correct	540 ms	448 KB	Output is correct
5	Correct	538 ms	344 KB	Output is correct
6	Correct	529 ms	348 KB	Output is correct
7	Correct	531 ms	344 KB	Output is correct
8	Correct	533 ms	440 KB	Output is correct
9	Correct	528 ms	436 KB	Output is correct
10	Correct	528 ms	344 KB	Output is correct
11	Correct	528 ms	436 KB	Output is correct
12	Correct	538 ms	600 KB	Output is correct
13	Correct	526 ms	432 KB	Output is correct
14	Correct	530 ms	440 KB	Output is correct
15	Correct	536 ms	344 KB	Output is correct
16	Incorrect	628 ms	344 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	344 KB	Output is correct
2	Correct	528 ms	348 KB	Output is correct
3	Correct	541 ms	596 KB	Output is correct
4	Correct	540 ms	448 KB	Output is correct
5	Correct	538 ms	344 KB	Output is correct
6	Correct	529 ms	348 KB	Output is correct
7	Correct	531 ms	344 KB	Output is correct
8	Correct	533 ms	440 KB	Output is correct
9	Correct	528 ms	436 KB	Output is correct
10	Correct	528 ms	344 KB	Output is correct
11	Correct	528 ms	436 KB	Output is correct
12	Correct	538 ms	600 KB	Output is correct
13	Correct	526 ms	432 KB	Output is correct
14	Correct	530 ms	440 KB	Output is correct
15	Correct	536 ms	344 KB	Output is correct
16	Incorrect	628 ms	344 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	344 KB	Output is correct
2	Correct	528 ms	348 KB	Output is correct
3	Correct	541 ms	596 KB	Output is correct
4	Correct	540 ms	448 KB	Output is correct
5	Correct	538 ms	344 KB	Output is correct
6	Correct	529 ms	348 KB	Output is correct
7	Correct	531 ms	344 KB	Output is correct
8	Correct	533 ms	440 KB	Output is correct
9	Correct	528 ms	436 KB	Output is correct
10	Correct	528 ms	344 KB	Output is correct
11	Correct	528 ms	436 KB	Output is correct
12	Correct	538 ms	600 KB	Output is correct
13	Correct	526 ms	432 KB	Output is correct
14	Correct	530 ms	440 KB	Output is correct
15	Correct	536 ms	344 KB	Output is correct
16	Incorrect	628 ms	344 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	344 KB	Output is correct
2	Correct	528 ms	348 KB	Output is correct
3	Correct	541 ms	596 KB	Output is correct
4	Correct	540 ms	448 KB	Output is correct
5	Correct	538 ms	344 KB	Output is correct
6	Correct	529 ms	348 KB	Output is correct
7	Correct	531 ms	344 KB	Output is correct
8	Correct	533 ms	440 KB	Output is correct
9	Correct	528 ms	436 KB	Output is correct
10	Correct	528 ms	344 KB	Output is correct
11	Correct	528 ms	436 KB	Output is correct
12	Correct	538 ms	600 KB	Output is correct
13	Correct	526 ms	432 KB	Output is correct
14	Correct	530 ms	440 KB	Output is correct
15	Correct	536 ms	344 KB	Output is correct
16	Incorrect	628 ms	344 KB	Output isn't correct
17	Halted	0 ms	0 KB	-