QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657717#7015. Rikka with IlluminationsexpectantWA 3ms34300kbC++142.5kb2024-10-19 15:20:062024-10-19 15:20:06

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 15:20:06]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:34300kb
  • [2024-10-19 15:20:06]
  • 提交

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.