Submission #119308

#	Time	Username	Problem	Language	Result	Execution time	Memory
119308		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	75 / 100	536 ms	37352 KiB

circuit

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=2e5;
int n, b[mxN], c[mxN+1], e1[mxN], e2[mxN];
array<ll, 2> a[mxN+1];
vector<int> va[mxN], vr[mxN], vp[mxN], ans;

bool cw(int x, int y, int z) {
	return (a[z][1]-a[x][1])*(a[y][0]-a[x][0])<(a[y][1]-a[x][1])*(a[z][0]-a[x][0]);
}

bool pcmp(const int &i, const int &j) {
	return a[i][1]*a[j][0]<a[j][1]*a[i][0];
}

struct scmp {
	bool operator()(const int &i, const int &j) const {
		if(e1[i]==e1[j])
			return c[e2[i]]<c[e2[j]]?!cw(e1[j], e2[j], e2[i]):cw(e1[i], e2[i], e2[j]);
		return c[e1[i]]<c[e1[j]]?cw(e1[i], e2[i], e1[j]):!cw(e1[j], e2[j], e1[i]);
	}
};
set<int, scmp> s;

int main() {
	scanf("%d", &n);
	for(int i=0; i<n; ++i)
		scanf("%d%d", &a[i][0], &a[i][1]);
	a[n]=a[0];
	iota(b, b+n, 0);
	sort(b, b+n, pcmp);
	for(int i=0; i<n; ++i) {
		c[i]=lower_bound(b, b+n, i, pcmp)-b;
		vp[c[i]].push_back(i);
	}
	c[n]=c[0];
	for(int i=0; i<n; ++i) {
		e1[i]=i;
		e2[i]=i+1;
		if(c[e2[i]]<c[e1[i]])
			swap(e1[i], e2[i]);
		if(c[e1[i]]<c[e2[i]]) {
			va[c[e1[i]]].push_back(i);
			vr[c[e2[i]]].push_back(i);
		}
	}
	for(int i=0; i<n; ++i) {
		for(int j : vr[i])
			s.erase(j);
		for(int j : va[i])
			s.insert(j);
		int mj=-1;
		for(int j : vp[i])
			if(mj<0||a[j][0]+a[j][1]<a[mj][0]+a[mj][1])
				mj=j;
		if(~mj&&(!s.size()||!cw(e1[*s.begin()], e2[*s.begin()], mj)))
			ans.push_back(mj);
	}
	printf("%d\n", ans.size());
	sort(ans.begin(), ans.end());
	for(int a : ans)
		printf("%d ", a+1);
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:31:35: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'std::array<long long int, 2>::value_type* {aka long long int*}' [-Wformat=]
   scanf("%d%d", &a[i][0], &a[i][1]);
                                   ^
circuit.cpp:31:35: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'std::array<long long int, 2>::value_type* {aka long long int*}' [-Wformat=]
circuit.cpp:62:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
circuit.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circuit.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i][0], &a[i][1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 75 / 100