Submission #202489

#	Time	Username	Problem	Language	Result	Execution time	Memory
202489		orihehe	Drvca (COCI19_drvca)	C++17	110 / 110	137 ms	7420 KiB

drvca

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#include <iostream>
#include <string>
#include <ctime>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pci pair<char,int>
#define pdd pair<double,double>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pdi pair<double,int>
#define pdd pair<double,double>
#define mod 1000000000
#define mod1 1000000009
#define mod2 1000000021
#define INF 2000000001
#define MAX 9000001
long double PI = 3.141592653589793238462643383279502884197;
using namespace std;

/* 🐣🐥 */
int arr[100001];
int n;
multiset<int> sss, A, B;
bool solve(int t, int srt) {
	sss.clear();
	A.clear(), B.clear();
	for (int i = 0; i < n; i++) sss.insert(arr[i]);
	while (true) {
		if (sss.find(srt) != sss.end()) {
			A.insert(srt);
			sss.erase(sss.find(srt));
		}
		else break;
		srt += t;
	}
	if (sss.size() == 0) {
		printf("%d\n", A.size() - 1);
		int cnt = 0;
		for (auto iter = A.begin(); ++cnt < A.size(); ++iter) 
			printf("%d ", *iter);
		printf("\n1\n%d", *(--A.end()));
		return true;
	}
	if (sss.size() <= 2) {
		printf("%d\n", A.size());
		for (auto iter = A.begin(); iter != A.end(); ++iter)
			printf("%d ", *iter);
		printf("\n%d\n", sss.size());
		for (auto iter = sss.begin(); iter != sss.end(); ++iter)
			printf("%d ", *iter);
		return true;
	}
	else {
		int ed = *(--A.end());
		bool flag = false;
		srt = *sss.begin();
		auto e = --sss.end();
		t = min(*(++sss.begin()) - srt, *(--sss.end()) - *(--e));
		while (!sss.empty()) {
			if (sss.find(srt) == sss.end()) {
				if (A.count(srt)) {
					A.erase(A.find(srt));
					B.insert(srt);
					srt += t;
					flag = true;
					continue;
				}
				else return false;
			}
			B.insert(srt);
			sss.erase(sss.find(srt));
			srt += t;
		}
		while (flag && A.find(srt) != A.end()) {
			A.erase(A.find(srt));
			B.insert(srt);
			srt += t;
		}
		if (flag && A.find(ed) != A.end()) return false;
		if (A.size() == 0) return false;
		printf("%d\n", A.size());
		for (auto iter = A.begin(); iter != A.end(); ++iter)
			printf("%d ", *iter);
		printf("\n%d\n", B.size());
		for (auto iter = B.begin(); iter != B.end(); ++iter)
			printf("%d ", *iter);
		return true;
	}
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
	if (n == 2) {
		printf("1\n%d\n1\n%d\n", arr[0], arr[1]);
		return 0;
	}
	sort(arr, arr + n);
	if (solve(arr[1] - arr[0], arr[0])) return 0;
	if (solve(arr[2] - arr[0], arr[0])) return 0;
	if (solve(arr[2] - arr[1], arr[1])) return 0;
	printf("-1");
}

Compilation message (stderr)

drvca.cpp: In function 'bool solve(int, int)':
drvca.cpp:51:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", A.size() - 1);
                  ~~~~~~~~~~~~^
drvca.cpp:53:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (auto iter = A.begin(); ++cnt < A.size(); ++iter) 
                               ~~~~~~^~~~~~~~~~
drvca.cpp:59:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", A.size());
                  ~~~~~~~~^
drvca.cpp:62:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("\n%d\n", sss.size());
                    ~~~~~~~~~~^
drvca.cpp:95:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", A.size());
                  ~~~~~~~~^
drvca.cpp:98:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("\n%d\n", B.size());
                    ~~~~~~~~^
drvca.cpp: In function 'int main()':
drvca.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
drvca.cpp:107:35: 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", &arr[i]);
                              ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30