oj.uz

Submission #119307

# Submission time Handle Problem Language Result Execution time Memory
119307 2019-06-21T02:22:26 Z tmwilliamlin168 Printed Circuit Board (CEOI12_circuit) C++14
0 / 100
 100 ms 16384 KB 
#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() {
	//ios::sync_with_stdio(0);
	//cin.tie(0);

	//cin >> n;
	scanf("%d", &n);
	while(n>mxN-1);
	for(int i=0; i<n; ++i)
		//cin >> a[i][0] >> a[i][1];
		scanf("%d%d", &a[i][0], &a[i][1]);
	a[n]=a[0];
	iota(b, b+n, 0);
	return 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);
	}
	//cout << ans.size() << "\n";
	printf("%d\n", ans.size());
	sort(ans.begin(), ans.end());
	for(int a : ans)
		//cout << a+1 << " ";
		printf("%d ", a+1);
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:37: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:37: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:70: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:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
circuit.cpp:37: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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14464 KB Output isn't correct
2 Incorrect 13 ms 14592 KB Output isn't correct
3 Incorrect 14 ms 14464 KB Output isn't correct
4 Incorrect 14 ms 14464 KB Output isn't correct
5 Incorrect 16 ms 14592 KB Output isn't correct
6 Incorrect 16 ms 14592 KB Output isn't correct
7 Incorrect 19 ms 14848 KB Output isn't correct
8 Incorrect 17 ms 14592 KB Output isn't correct
9 Incorrect 15 ms 14592 KB Output isn't correct
10 Incorrect 16 ms 14592 KB Output isn't correct
11 Incorrect 17 ms 14592 KB Output isn't correct
12 Incorrect 17 ms 14848 KB Output isn't correct
13 Incorrect 20 ms 14976 KB Output isn't correct
14 Incorrect 21 ms 15224 KB Output isn't correct
15 Incorrect 23 ms 15360 KB Output isn't correct
16 Incorrect 32 ms 16384 KB Output isn't correct
17 Incorrect 36 ms 16376 KB Output isn't correct
18 Execution timed out 1076 ms 14336 KB Time limit exceeded
19 Execution timed out 1071 ms 14464 KB Time limit exceeded
20 Execution timed out 1069 ms 14336 KB Time limit exceeded