oj.uz

Submission #577651

# Submission time Handle Problem Language Result Execution time Memory
577651 2022-06-15T07:27:41 Z temporary_juggernaut Roads (CEOI20_roads) C++14
30 / 100
 183 ms 22024 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
pair<ll,ll>a[100005];
pair<ll,ll>b[100005];
int n;
const int inf=1e9;
bool cmp(pair<pair<ll,ll>,pair<ll,ll>>&l,pair<pair<ll,ll>,pair<ll,ll>>&r){
	return l.fr.fr*r.fr.sc>r.fr.fr*l.fr.sc;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc);
	if(a[1].fr==b[1].fr){
		//VERTICAL
		map<int,vector<int>>mp;		
		for(int i=1;i<=n;i++){
			mp[a[i].fr].push_back(a[i].sc);
			mp[a[i].fr].push_back(b[i].sc);
		}
		int prev=inf;
		for(auto &tmp:mp){
			int a=tmp.fr;
			vector<int>&b=tmp.sc;
			sort(b.begin(),b.end());
			for(int i=1;i+1<(int)b.size();i+=2)
				printf("%d %d %d %d\n",a,b[i],a,b[i+1]);
			if(prev^inf)
				printf("%d %d %d %d\n",prev,mp[prev][0],a,b[0]);
			prev=a;
		}
	}else{
		map<pair<ll,ll>,vector<pair<ll,ll>>>mp;		
		for(int i=1;i<=n;i++){
			pair<ll,ll>cur;
			ll &x0=a[i].fr;
			ll &x1=b[i].fr;
			ll &y0=a[i].sc;
			ll &y1=b[i].sc;
			cur=make_pair(x0*y1-x1*y0,x0-x1);
			if(cur.sc<0){
				cur.fr*=-1;
				cur.sc*=-1;
			}
			ll tmp=__gcd(abs(cur.fr),cur.sc);
			cur.fr/=tmp;
			cur.sc/=tmp;
			mp[cur].push_back(a[i]);
			mp[cur].push_back(b[i]);
		}
		vector<pair<pair<ll,ll>,pair<ll,ll>>>vec;
		for(auto &tmp:mp){
			vector<pair<ll,ll>>&b=tmp.sc;
			sort(b.begin(),b.end());
			for(int i=1;i+1<(int)b.size();i+=2)
				printf("%lld %lld %lld %lld\n",b[i].fr,b[i].sc,b[i+1].fr,b[i+1].sc);
			vec.push_back(make_pair(tmp.fr,b[0]));
		}
		sort(vec.begin(),vec.end(),cmp);
		for(int i=1;i<vec.size();i++)printf("%lld %lld %lld %lld\n",vec[i-1].sc.fr,vec[i-1].sc.sc,vec[i].sc.fr,vec[i].sc.sc);
	}
}

Compilation message

roads.cpp: In function 'int main()':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=1;i<vec.size();i++)printf("%lld %lld %lld %lld\n",vec[i-1].sc.fr,vec[i-1].sc.sc,vec[i].sc.fr,vec[i].sc.sc);
      |               ~^~~~~~~~~~~
roads.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
roads.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%lld%lld%lld%lld",&a[i].fr,&a[i].sc,&b[i].fr,&b[i].sc);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 212 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 11 ms 2004 KB Output is correct
5 Correct 26 ms 3700 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 12 ms 2004 KB Output is correct
5 Correct 25 ms 3600 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 14 ms 2512 KB Output is correct
10 Correct 183 ms 22024 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 13 ms 2004 KB Output is correct
5 Correct 24 ms 3640 KB Output is correct
6 Failed 1 ms 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 212 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 212 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -