QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246915 | #7680. Subway | ucup-team052# | WA | 1ms | 3996kb | C++14 | 2.2kb | 2023-11-11 12:09:06 | 2023-11-11 12:09:06 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=55;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(0);
int brand(){return rng()&0X7FFFFFFF;}
int n,cur[N];
struct vec{
int x,y,tt;
vec operator-(const vec&rhs)const{return (vec){x-rhs.x,y-rhs.y,0};}
vec operator+(const vec&rhs)const{return (vec){x+rhs.x,y+rhs.y,0};}
vec operator*(const int&k)const{return (vec){x*k,y*k,0};}
}a[N],w[N];
LL cross(vec a,vec b){return 1LL*a.x*b.y-1LL*a.y*b.x;}
vec Get(vec a,vec b){
return a+b;
}
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
rd(n);
int ans=0;
rep(i,1,n){
rd(a[i].x),rd(a[i].y),rd(a[i].tt);
ans=max(ans,a[i].tt);
}
if(n==1){
a[++n]=a[1];
++a[2].x;
}
vec bg;
auto test=[&](){
rep(i,1,n){
rep(j,i+1,n){
if(cross(a[i]-bg,a[j]-bg)==0){
return 0;
}
}
}
return 1;
};
const int X=n==2?3:-1001;
while(1){
bg=(vec){-X-brand()%X,-X-brand()%X};
if(test())break;
}
sort(a+1,a+n+1,[&](vec a,vec b){return cross(a-bg,b-bg)>0;});
rep(i,1,n-1){
w[i]=Get(a[i]-bg,a[i+1]-bg);
}
rep(i,1,n){
cur[i]=0;
}
printf("%d\n",ans);
rep(_,1,ans){
vector<vec>v;
rep(i,1,n){
if(a[i].tt){
--a[i].tt;
v.pb(a[i]);
}else{
++cur[i];
v.pb(a[i]+(a[i]-bg)*cur[i]);
}
if(i<n){
v.pb(bg+w[i]*_);
}
}
printf("%d ",SZ(v));
for(auto&[x,y,z]:v)printf("%d %d ",x,y);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3996kb
input:
3 1 2 1 2 1 2 3 3 2
output:
2 5 1 2 -44 -773 2 1 -42 -772 3 3 5 -45 -772 -135 -2322 2 1 -131 -2320 3 3
result:
ok ok Sum L = 10
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 1 1 1
output:
1 3 2 1 6 6 1 1
result:
ok ok Sum L = 3
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3796kb
input:
1 1 1 50
output:
50 3 2 1 6 6 1 1 3 2 1 15 16 1 1 3 2 1 24 26 1 1 3 2 1 33 36 1 1 3 2 1 42 46 1 1 3 2 1 51 56 1 1 3 2 1 60 66 1 1 3 2 1 69 76 1 1 3 2 1 78 86 1 1 3 2 1 87 96 1 1 3 2 1 96 106 1 1 3 2 1 105 116 1 1 3 2 1 114 126 1 1 3 2 1 123 136 1 1 3 2 1 132 146 1 1 3 2 1 141 156 1 1 3 2 1 150 166 1 ...
result:
wrong answer Polyline 2 intersects with previous polylines.