Submission #345827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
345827	2021-01-08T08:59:15 Z	kshitij_sodani	Arranging Tickets (JOI17_arranging_tickets)	C++14	10 / 100	1184 ms	504 KB

arranging_tickets

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
int n,m;
int aa[200001];
int bb[200001];
int cc[200001];
int co[200001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>aa[i]>>bb[i]>>cc[i];
		aa[i]--;
		bb[i]--;
	}
	int ans=m;
	for(int i=0;i<(1<<m);i++){
		for(int j=0;j<n;j++){
			co[j]=0;
		}
		for(int j=0;j<m;j++){
			if(i&(1<<j)){
				int cur=aa[j];
				while(cur!=bb[j]){
					co[cur]++;
					cur=(cur+1)%n;
				}
			}
			else{
				int cur=bb[j];
				while(cur!=aa[j]){
					co[cur]++;
					cur=(cur+1)%n;
				}
			}
		}
		int ma=0;
		for(int j=0;j<n;j++){
			ma=max(ma,co[j]);
		}
		ans=min(ans,ma);
	}

	cout<<ans<<endl;



 
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1179 ms	492 KB	Output is correct
2	Correct	1180 ms	364 KB	Output is correct
3	Correct	1184 ms	364 KB	Output is correct
4	Correct	1166 ms	420 KB	Output is correct
5	Correct	1183 ms	492 KB	Output is correct
6	Correct	1173 ms	504 KB	Output is correct
7	Correct	1180 ms	492 KB	Output is correct
8	Correct	1181 ms	420 KB	Output is correct
9	Correct	1177 ms	492 KB	Output is correct
10	Correct	1170 ms	492 KB	Output is correct
11	Correct	1179 ms	492 KB	Output is correct
12	Correct	1177 ms	492 KB	Output is correct
13	Correct	1172 ms	376 KB	Output is correct
14	Correct	1177 ms	420 KB	Output is correct
15	Correct	1179 ms	364 KB	Output is correct

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1179 ms	492 KB	Output is correct
2	Correct	1180 ms	364 KB	Output is correct
3	Correct	1184 ms	364 KB	Output is correct
4	Correct	1166 ms	420 KB	Output is correct
5	Correct	1183 ms	492 KB	Output is correct
6	Correct	1173 ms	504 KB	Output is correct
7	Correct	1180 ms	492 KB	Output is correct
8	Correct	1181 ms	420 KB	Output is correct
9	Correct	1177 ms	492 KB	Output is correct
10	Correct	1170 ms	492 KB	Output is correct
11	Correct	1179 ms	492 KB	Output is correct
12	Correct	1177 ms	492 KB	Output is correct
13	Correct	1172 ms	376 KB	Output is correct
14	Correct	1177 ms	420 KB	Output is correct
15	Correct	1179 ms	364 KB	Output is correct
16	Incorrect	974 ms	492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1179 ms	492 KB	Output is correct
2	Correct	1180 ms	364 KB	Output is correct
3	Correct	1184 ms	364 KB	Output is correct
4	Correct	1166 ms	420 KB	Output is correct
5	Correct	1183 ms	492 KB	Output is correct
6	Correct	1173 ms	504 KB	Output is correct
7	Correct	1180 ms	492 KB	Output is correct
8	Correct	1181 ms	420 KB	Output is correct
9	Correct	1177 ms	492 KB	Output is correct
10	Correct	1170 ms	492 KB	Output is correct
11	Correct	1179 ms	492 KB	Output is correct
12	Correct	1177 ms	492 KB	Output is correct
13	Correct	1172 ms	376 KB	Output is correct
14	Correct	1177 ms	420 KB	Output is correct
15	Correct	1179 ms	364 KB	Output is correct
16	Incorrect	974 ms	492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1179 ms	492 KB	Output is correct
2	Correct	1180 ms	364 KB	Output is correct
3	Correct	1184 ms	364 KB	Output is correct
4	Correct	1166 ms	420 KB	Output is correct
5	Correct	1183 ms	492 KB	Output is correct
6	Correct	1173 ms	504 KB	Output is correct
7	Correct	1180 ms	492 KB	Output is correct
8	Correct	1181 ms	420 KB	Output is correct
9	Correct	1177 ms	492 KB	Output is correct
10	Correct	1170 ms	492 KB	Output is correct
11	Correct	1179 ms	492 KB	Output is correct
12	Correct	1177 ms	492 KB	Output is correct
13	Correct	1172 ms	376 KB	Output is correct
14	Correct	1177 ms	420 KB	Output is correct
15	Correct	1179 ms	364 KB	Output is correct
16	Incorrect	974 ms	492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1179 ms	492 KB	Output is correct
2	Correct	1180 ms	364 KB	Output is correct
3	Correct	1184 ms	364 KB	Output is correct
4	Correct	1166 ms	420 KB	Output is correct
5	Correct	1183 ms	492 KB	Output is correct
6	Correct	1173 ms	504 KB	Output is correct
7	Correct	1180 ms	492 KB	Output is correct
8	Correct	1181 ms	420 KB	Output is correct
9	Correct	1177 ms	492 KB	Output is correct
10	Correct	1170 ms	492 KB	Output is correct
11	Correct	1179 ms	492 KB	Output is correct
12	Correct	1177 ms	492 KB	Output is correct
13	Correct	1172 ms	376 KB	Output is correct
14	Correct	1177 ms	420 KB	Output is correct
15	Correct	1179 ms	364 KB	Output is correct
16	Incorrect	974 ms	492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-