Submission #1316715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316715		athena	Towers (NOI22_towers)	C++20	16 / 100	2096 ms	85468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
//#define int long long int
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    cin>>n;
    vector<pair<int,int>>edge(n);
    vector<vector<int>>xx(1e6+1);
    vector<vector<int>>yy(1e6+1);
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        edge[i]={x,y};
        xx[x].push_back(y);
        yy[y].push_back(x);
    }
    for(int mask=0;mask<(1<<n);mask++)
    {int sm=0;int ll=0;
    int sm2=0;int ll2=0;
      int c=1;
      bool ok=true;
     // cout<<"MASK"<<endl;
       //for(int i=0;i<n;i++)
       // {
          //  if(mask&(1<<i))cout<<1;
           // else
            //    cout<<0;
      //  }
       // cout<<endl;
        for(int i=0;i<n;i++)
        {c=1;
            if(mask&(1<<i))//if tower
            {//check if no of towers exceed 2
                auto [x,y]=edge[i];
               // cout<<"EDGE "<<i<<endl;
                for(int u:xx[x])
                {
                    //find the i of this edge
                    int ind=0;
                    for(int j=0;j<n;j++)
                    {
                        if(edge[j].first==x&&edge[j].second==u)//found j
                        {
                           ind=j;
                         //  cout<<"J "<<j<<endl;
                           break;
                        }
                    }
                    if(ind!=i){
                    if(mask&(1<<ind))
                    {
                     c++;
                    // cout<<"IND "<<ind<<" C "<<c<<endl;
                    }
                    }
                    if(c>2){
                        ok=false;
                       // cout<<"HEY"<<endl;
                     break;
                    }
                }
                if(!ok)break;
                c=1;
                 for(int u:yy[y])
                {
                    //find the i of this edge
                    int ind=0;
                    for(int j=0;j<n;j++)
                    {
                        if(edge[j].first==u&&edge[j].second==y)//found j
                        {
                          
                           ind=j;
                    //         cout<<"IND "<<ind<<endl;
                           break;
                        }
                    }if(ind!=i){
                    if(mask&(1<<ind))
                    {
                     c++;
                    }
                    }
                    if(c>2){//cout<<"MEOW"<<endl;
                    ok=false;
                     break;
                    }
                }
                if(!ok)break;
            }
            else
            {   //find node in my adj
               // ll=0;sm=0;
               ok=false;
                   auto [x,y]=edge[i];
               // cout<<"EDGE "<<i<<endl;
               bool hy=false,ly=false;
                for(int u:xx[x])
                {
                 //   cout<<"U "<<u<<endl;
                      int ind=-1;
                     for(int j=0;j<n;j++)
                    {
                        if(edge[j].first==x&&edge[j].second==u)//found j
                        {
                           ind=j;
                           break;
                        }
                    }
                     if(ind==-1)continue;
                    if(!(mask&(1<<ind)))continue;
                  
                    if(u<y)
                    {
                     ly=true;
                    }
                    if(u>y)
                    {
                     hy=true;
                    }
                }
                
                bool hx=false,lx=false;
                for(int u:yy[y])
                {
                     int ind=-1;
                     for(int j=0;j<n;j++)
                    {
                        if(edge[j].first==u&&edge[j].second==y)//found j
                        {
                           ind=j;
                           break;
                        }
                    }
                    if(ind==-1)continue;
                    if(!(mask&(1<<ind)))continue;
                    
                    if(u<x)
                    {
                        lx=true;
                    }
                    if(u>x)
                    {
                        hx=true;
                    }
                }
              bool cc=(hx&&lx)||(hy&&ly);
              if(!cc){ok=false;break;}
              else
              ok=true;
            }

        }
        if(!ok)continue;
        //if((ll!=1||sm!=1)&&(ll2!=1||sm2!=1))continue;
        for(int i=0;i<n;i++)
        {
            if(mask&(1<<i))cout<<1;
            else
                cout<<0;
        }
        break;
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19