Submission #824646

#	Time	Username	Problem	Language	Result	Execution time	Memory
824646		kshitij_sodani	Rope (JOI17_rope)	C++17	45 / 100	2552 ms	980 KiB

rope

#include <bits/stdc++.h>
#define a first
#define b second
#define pb push_back
using namespace std;
#define endl '\n'
typedef long long llo;


int it[1000001];
int ans[1000001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		ans[i]=n;
	}
	for(int i=0;i<n;i++){
		cin>>it[i];
		it[i]--;
		ans[it[i]]--;
	}
	
	for(int i=0;i<m;i++){
		for(int j=i+1;j<m;j++){
			for(int k=0;k<2;k++){
				pair<int,int> pr={-1,-1};
				int co=0;
				for(int l=0;l<n;l++){
					if(it[l]==i or it[l]==j){
						co++;

						if(pr.a==-1){
							pr={l,it[l]};
						}
						else if(it[l]==pr.b){
							pr={l,it[l]};
						}
						else if(pr.a<l-1){
							pr={l,it[l]};
						}
						else{
							if((pr.a)%2==k){
								pr={l,it[l]};
							}
							else{
								
								co--;
								continue;
							}
						}
					}
				}
				ans[i]=min(ans[i],n-co);
				ans[j]=min(ans[j],n-co);
			}
		}
	}

	for(int i=0;i<m;i++){
		cout<<ans[i]<<endl;

	}






	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20