Submission #119308

#TimeUsernameProblemLanguageResultExecution timeMemory
119308tmwilliamlin168Printed Circuit Board (CEOI12_circuit)C++14
75 / 100
536 ms37352 KiB
#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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...