Submission #128508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
128508	2019-07-11T04:43:25 Z	임유진(#3161)	Rope (JOI17_rope)	C++14	Compilation error	0 ms	0 KB

rope

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 1000005
#define MAXM 5005

typedef pair<int, int> pii;

int C[MAXN];
int A[MAXM];
pii as[MAXN];
vector<int> cha[MAXM][2];

int main() {
	int N, M;

	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; i++) scanf("%d", C + i);

	for(int i = 0; i < N; i++) A[C[i]]++;
	for(int i = 0; i < N - 1; i++) if(C[i] != C[i + 1]) {
		cha[C[i]][i % 2].push_back(C[i + 1]);
		cha[C[i + 1]][i % 2].push_back(C[i]);
	}
	for(int i = 1; i <= M; i++) {
		sort(cha[i][0].begin(), cha[i][0].end());
		sort(cha[i][1].begin(), cha[i][1].end());
	}
	for(int i = 1; i <= M; i++) as[i - 1] = make_pair(A[i], i);
	sort(as, as + M, greater<pii>());

	//for(int i = 0; i < M; i++) printf("(%d, %d)", as[i].first, as[i].second);

	for(int i = 1; i <= M; i++) {
		int mn = N - A[i];
		for(int j = 0; j < M; j++) if(as[j].second != i) {
			if(!binary_search(cha[i][0].begin(), cha[i][0].end(), as[j].second) && !binary_search(cha[i][1].begin(), cha[i][1].end(), as[j].second)) {
				//printf("i = %d, as[j] = (%d, %d)\n", i, as[j].first, as[j].second);
				mn = min(mn, N - A[i] - as[j].first);
				break;
			}
		}
		for(auto a : cha[i][0]) {
			//printf("i = %d, a = %d\n", i, a);
			int cnt0 = upper_bound(cha[i][0].begin(), cha[i][0].end(), a) - lower_bound(cha[i][0].begin(), cha[i][0].end(), a);
			int cnt1 = upper_bound(cha[i][1].begin(), cha[i][1].end(), a) - lower_bound(cha[i][1].begin(), cha[i][1].end(), a);
			mn = min(mn, N - A[i] - A[a] + min(cnt0, cnt1));
		}
		for(auto a : cha[i][1]) {
			//printf("i = %d, a = %d\n", i, a);
			int cnt0 = upper_bound(cha[i][0].begin(), cha[i][0].end(), a) - lower_bound(cha[i][0].begin(), cha[i][0].end(), a);
			int cnt1 = upper_bound(cha[i][1].begin(), cha[i][1].end(), a) - lower_bound(cha[i][1].begin(), cha[i][1].end(), a);
			mn = min(mn, N - A[i] - A[a] + min(cnt0, cnt1));
		}
		printf("%d\n", mn);
	}

	return 0;
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:33:19: error: 'greater' was not declared in this scope
  sort(as, as + M, greater<pii>());
                   ^~~~~~~
rope.cpp:33:30: error: expected primary-expression before '>' token
  sort(as, as + M, greater<pii>());
                              ^
rope.cpp:33:32: error: expected primary-expression before ')' token
  sort(as, as + M, greater<pii>());
                                ^
rope.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
rope.cpp:21:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%d", C + i);
                             ~~~~~^~~~~~~~~~~~~