Submission #1316712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316712		athena	Towers (NOI22_towers)	C++20	0 / 100	2097 ms	99240 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t 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;
     // 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){
                       // cout<<"HEY"<<endl;
                     break;
                    }
                }
                if(c>2)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;
                     break;
                    }
                }
                if(c>2)break;
            }
            else
            {   //find node in my adj
                ll=0;sm=0;
                   auto [x,y]=edge[i];
               // cout<<"EDGE "<<i<<endl;
                for(int u:xx[x])
                {
                 //   cout<<"U "<<u<<endl;
                      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(u<y&&ll==0)
                    {//find the index of u
                  
                        if(mask&(1<<ind)){
                            //cout<<"FOUND LOWER X"<<endl;
                        ll=1;
                        }
                    }
                    if(u>y&&sm==0)
                    {
                        
                        if(mask&(1<<ind)){
                           // cout<<"FOUND LOWER X"<<endl;
                        sm=1;
                        }
                    }
                }
                ll2=0;sm2=0;
                for(int u:yy[y])
                {
                     int ind=0;
                     for(int j=0;j<n;j++)
                    {
                        if(edge[j].first==u&&edge[j].second==y)//found j
                        {
                           ind=j;
                        //   cout<<"J "<<j<<endl;
                           break;
                        }
                    }
                    if(u<x&&ll2==0)
                    {
                        if(mask&(1<<ind))
                        ll2=1;
                    }
                    if(u>x&&sm2==0)
                    {
                        if(mask&(1<<ind))
                        sm2=1;
                    }
                }
              
                
                if((ll!=1||sm!=1)&&(ll2!=1||sm2!=1)){
                //    cout<<"CRARA"<<" "<<ll<<" "<<sm<<" "<<ll2<<" "<<sm2<<endl;
                    break;
                }
            }

        }
        if(c>2)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: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19