Submission #703008

#	Time	Username	Problem	Language	Result	Execution time	Memory
703008		NemanjaSo2005	Pinball (JOI14_pinball)	C++14	0 / 100	1072 ms	1952 KiB

pinball

#include<bits/stdc++.h>
#define ll long long
using namespace std;
/// N<=300
/// M<=2000
const string test="01";
ll N,M,L,degree[505],niz[505],pozicija[505],koji[505];
vector<int> graf[505];
struct cord{
    int x,y,id;
} tacke[505];
bool pox(cord x,cord y){
    return x.x<y.x;
}
struct grana{
    int a,b;
} grane[2005];
bool podeg(int a,int b){
    return degree[a]>degree[b];
}
vector<int> V;
void msbacaj(int L,int R){
    if(R<L)
        return;
    int mid=(L+R)/2;
    V.push_back(mid);
    msbacaj(L,mid-1);
    msbacaj(mid+1,R);
    return;
}
int znak(int a){
    if(a>0)
        return 1;
    if(a==0)
        return 0;
    return -1;
}
int strana(cord a,cord b,cord c){
    return (c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.x-a.x);
}
bool seku(cord a1,cord b1,cord a2,cord b2){
    if(strana(a1,b1,a2)*strana(a1,b1,b2)>0)
        return false;
    if(strana(a2,b2,a1)*strana(a2,b2,b1)>0)
        return false;
    return true;
}
int prebroj(){
    int ret=0;
    for(int i=1;i<=M;i++){
        for(int j=i+1;j<=M;j++){
            ret+=seku(tacke[pozicija[grane[i].a]],tacke[pozicija[grane[i].b]],tacke[pozicija[grane[j].a]],tacke[pozicija[grane[j].b]]);
        }
    }
    return ret;
}
void zameni(int a,int b){
    if(koji[a]==0)
        pozicija[koji[b]]=a;
    else if(koji[b]==0)
        pozicija[koji[b]]=a;
    else
        swap(pozicija[koji[a]],pozicija[koji[b]]);
    swap(koji[a],koji[b]);
}
struct slog{
    int koji,gde;
}pp;
queue<slog> Q;
queue<int> K;
int prosli[505],stavio[505];
int pvred,svred;
void stavi(){
    pvred++;
    int tren,tpoz;
    pp.koji=niz[1];
    pp.gde=L/2;
    Q.push(pp);
    while(Q.size()){
        tren=Q.front().koji;
        tpoz=Q.front().gde;
        Q.pop();
        if(prosli[tren]==pvred)
            continue;
        prosli[tren]=pvred;
        while(K.size())
            K.pop();
        if(pozicija[tren]==0){
            pozicija[tren]=tpoz;
            koji[tpoz]=tren;
        }
        svred++;
        int ml=1e9,vl=0,md=1e9,vd=0;
        for(int i=1;i<=L;i++){
            int gde=tpoz-i;
            if(gde>=1)
            if(koji[gde]==0 and tacke[gde].y>vl or tacke[gde].y<ml){
                vl=max(vl,tacke[gde].y);
                ml=min(ml,tacke[gde].y);
                K.push(gde);
                stavio[gde]=svred;
            }
            gde=tpoz+i;
            if(gde>=1)
            if(koji[gde]==0 and tacke[gde].y>vd or tacke[gde].y<md){
                vd=max(vd,tacke[gde].y);
                md=min(md,tacke[gde].y);
                K.push(gde);
                stavio[gde]=svred;
            }
        }

        for(int i=1;i<=L;i++){
            int gde=tpoz-i;
            if(gde>=1)
            if(koji[gde]==0 and stavio[gde]<svred){
                K.push(gde);
                stavio[gde]=svred;
            }
            gde=tpoz+i;
            if(gde<=L)
            if(koji[gde]==0  and stavio[gde]<svred){
                K.push(gde);
                stavio[gde]=svred;
            }
        }

        for(int i=0;i<graf[tren].size();i++){
            if(koji[graf[tren][i]]!=0)
                continue;
            pp.gde=K.front();
            pp.koji=graf[tren][i];
            Q.push(pp);
            K.pop();
        }
    }
    return;
}
ofstream ouf;
void output(){
    ouf.open(test+".out");
    for(int i=1;i<=N;i++)
        ouf<<tacke[pozicija[i]].id<<endl;
    ouf.close();
    return;
}
mt19937_64 rng;
int main(){
    while(true){
        int x1,x2,y11,y2;
        cin>>x1>>y11>>x2>>y2;
        cord a,b,c,d;
        a.x=x1;
        a.y=y11;
        b.x=x2;
        b.y=y2;
        cin>>x1>>y11>>x2>>y2;
        c.x=x1;
        c.y=y11;
        d.x=x2;
        d.y=y2;
        cout<<seku(a,b,c,d)<<endl;
    }
    rng.seed(time(NULL));
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ifstream inf;
    inf.open(test+".txt");

    //#define cin inf
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        cin>>grane[i].a>>grane[i].b;
        degree[grane[i].a]++;
        degree[grane[i].b]++;
        graf[grane[i].a].push_back(grane[i].b);
        graf[grane[i].b].push_back(grane[i].a);
    }
    cin>>L;
    for(int i=1;i<=L;i++){
        cin>>tacke[i].x>>tacke[i].y;
        tacke[i].id=i;
    }
    for(int i=1;i<=N;i++){
        cin>>pozicija[i];
        koji[pozicija[i]]=i;
    }
    cout<<prebroj()<<endl;
    return 0;
    for(int i=1;i<=N;i++)
        sort(graf[i].begin(),graf[i].end(),podeg);
    for(int i=1;i<=N;i++)
        niz[i]=i;
    sort(niz+1,niz+1+N,podeg);
    msbacaj(1,L);
    sort(tacke+1,tacke+1+L,pox);
    for(int i=1;i<=N;i++){
        pozicija[i]=V[i-1];
        koji[V[i-1]]=i;
    }
    stavi();

    int nov,gmax,res=prebroj();
    gmax=res;
    int a,b;
    cout<<"SKOR JE "<<res<<endl;
    while(true){
        a=1;
        b=2;
        bool bolji=false;
        for(int a=1;a<=L;a++)
            for(int b=a+1;b<=L;b++){
                //cout<<a<<" "<<b<<endl;
                if(koji[a]==koji[b])
                    continue;
                zameni(a,b);
                nov=prebroj();
                if(nov<res){
                    bolji=true;
                    if(nov<gmax){
                        cout<<"SKOR JE SADA "<<nov<<endl;
                        output();
                        gmax=nov;
                    }
                    res=nov;

                    continue;
                }
                zameni(a,b);
        }
        if(bolji==false){
           for(int i=1;i<=N;i++){
                int x=rng()%L+1;
                while(koji[x]!=0)
                    x=rng()%L+1;
                pozicija[i]=x;
                koji[x]=i;
            }
            res=prebroj();
        }
    }


    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void stavi()':
pinball.cpp:97:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |             if(koji[gde]==0 and tacke[gde].y>vl or tacke[gde].y<ml){
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:105:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  105 |             if(koji[gde]==0 and tacke[gde].y>vd or tacke[gde].y<md){
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for(int i=0;i<graf[tren].size();i++){
      |                     ~^~~~~~~~~~~~~~~~~~
pinball.cpp: In function 'int main()':
pinball.cpp:205:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  205 |     int a,b;
      |         ^
pinball.cpp:205:11: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  205 |     int a,b;
      |           ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49