Submission #1316714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316714		athena	Towers (NOI22_towers)	C++20	16 / 100	2096 ms	85480 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 {
    auto [x, y] = edge[i];

    bool lowX = false, highX = false;
    for (int u : xx[x]) {
        int ind = -1;
        for (int j = 0; j < n; j++) {
            if (edge[j].first == x && edge[j].second == u) { ind = j; break; }
        }
        if (ind == -1) continue;
        if (!(mask & (1 << ind))) continue; // not a tower

        if (u < y) lowX = true;
        if (u > y) highX = true;
    }

    bool leftY = false, rightY = 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) { ind = j; break; }
        }
        if (ind == -1) continue;
        if (!(mask & (1 << ind))) continue; // not a tower

        if (u < x) leftY = true;
        if (u > x) rightY = true;
    }

    bool covered = (lowX && highX) || (leftY && rightY);
    if (!covered) { ok = false; break; }
}


        }
        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