QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#657717 | #7015. Rikka with Illuminations | expectant | WA | 3ms | 34300kb | C++14 | 2.5kb | 2024-10-19 15:20:06 | 2024-10-19 15:20:06 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define drp(i,j,k) for(int i=j;i>=(k);--i)
#define MAXN 1000005
typedef long long ll;
int task,n,m,l[MAXN],r[MAXN];
std::vector<int> vec[MAXN];
struct data{
int l,r,id;
inline bool operator < (const data &rhs)const{
return l<rhs.l;
}
}seq[MAXN],tmp[MAXN];
struct point{
ll x,y;
inline point operator + (const point &rhs)const{
return (point){x+rhs.x,y+rhs.y};
}
inline point operator - (const point &rhs)const{
return (point){x-rhs.x,y-rhs.y};
}
}a[MAXN],b[MAXN];
inline ll cross(const point &lhs,const point &rhs){
return lhs.x*rhs.y-lhs.y*rhs.x;
}
inline std::vector<int> solve(int x){
int cnt=0,id=0,pos=1,st=tmp[x].l,cur=tmp[x].r;
std::vector<int> ret;
ret.push_back(seq[x].id);
rep(i,x,m) tmp[++cnt]=seq[i];
rep(i,1,x-1) tmp[++cnt]=seq[i],tmp[cnt].l+=n,tmp[cnt].r+=n;
rep(i,st,st+n-1){
while(pos<cnt&&tmp[pos+1].l==i){
++pos;
if(tmp[pos].r>tmp[id].r) id=pos;
}
if(i==cur){
if(tmp[id].r<=i) return std::vector<int>();
cur=tmp[id].r,ret.push_back(tmp[id].id),id=0;
}
}
return ret;
}
inline void print(){
int pos=0;
rep(i,1,m) if(!vec[i].empty()&&(!pos||vec[i].size()<vec[pos].size())) pos=i;
if(!pos) std::cout<<-1<<'\n';
else{
std::cout<<vec[pos].size()<<'\n';
rep(i,0,(int)vec[pos].size()-1) std::cout<<vec[pos][i]<<" \n"[i==(int)vec[pos].size()-1];
}
}
inline void init(){
rep(i,1,m) std::vector<int>().swap(vec[i]);
}
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0),std::cout.tie(0);
std::cin>>task;
while(task--){
std::cin>>n>>m,init();
rep(i,1,n) std::cin>>a[i].x>>a[i].y;
std::reverse(a+1,a+n+1);
rep(i,1,m) std::cin>>b[i].x>>b[i].y;
rep(i,1,m){
int cntl=0,cntr=0;
rep(cur,1,n){
int lst=cur==1?n:cur-1,nxt=cur==n?1:cur+1;
if(cross(a[cur]-b[i],a[cur]-a[lst])>0&&cross(a[cur]-b[i],a[nxt]-a[cur])<0) ++cntl,l[i]=cur;
if(cross(a[cur]-b[i],a[cur]-a[lst])<0&&cross(a[cur]-b[i],a[nxt]-a[cur])>0) ++cntr,r[i]=cur;
}
assert(cntl==1&&cntr==1);
if(l[i]>r[i]) r[i]+=n;
seq[i]=(data){l[i],r[i],i};
}
std::sort(seq+1,seq+m+1);
rep(i,1,m) vec[i]=solve(i);
print();
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 34300kb
input:
1 3 3 0 0 1 0 0 1 -1 -1 3 -1 -1 3
output:
3 3 2 1
result:
wrong answer In case 1, the participant's output 3 is larger than the jury's 2.