Submission #202480

#	Time	Username	Problem	Language	Result	Execution time	Memory
202480		orihehe	Drvca (COCI19_drvca)	C++17	0 / 110	37 ms	1396 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() == 1) {
		printf("%d\n", A.size());
		for (auto iter = A.begin(); iter != A.end(); ++iter)
			printf("%d ", *iter);
		printf("\n1\n%d", *sss.begin());
		return true;
	}
	else if (sss.size() >= 2) {
		srt = *(sss.begin());
		t = *(++sss.begin()) - srt;
		while (!sss.empty()) {
			if (sss.find(srt) == sss.end()) return false;
			B.insert(srt);
			sss.erase(sss.find(srt));
			srt += t;
		}

		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;
	}
	vector<int> vec;
	sort(arr, arr + n);
	for (int i = 1; i < n; i++) {
		vec.push_back(arr[i] - arr[i-1]);
	}
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	if (vec.size() > 4) return !printf("-1");

	for (int i = vec.size() - 1; i >= 0; i--) {
		if (solve(vec[i], arr[0])) return 0;
		if (solve(vec[i], 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:75: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:78: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:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
drvca.cpp:87: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: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30