Submission #1302343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302343		tdoxsanh	Towers (NOI22_towers)	C++20	6 / 100	165 ms	39600 KiB

Main

#include <bits/stdc++.h>
//#include <windows.h>
//#include <conio.h>
#define N 1001001
#define M
#define CODE "SLAMP"
#define MOD
#define MOD1
#define MOD2
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define is insert
#define mkp make_pair
typedef int ui;
typedef long long ul;
typedef long double ud;
typedef std::pair<int,int> pii;
typedef std::pair<long long,long long> pll;
using namespace std;
constexpr int iinf=(int)1e9+7;
constexpr long long linf=(long long)1e18+7;
ui n;
pii p[N];
namespace Subtask_2
{
    bool check()
    {
        return n<=16;
    }
    vector<ui> ans;
    ui bin[N];
    struct st
    {
        ui fst,lst,cnt;
    }row[N],col[N];
    void reset()
    {
        ans.clear();
        for(ui i=1;i<N;i++)
        {
            row[i].fst=0;
            row[i].lst=0;
            row[i].cnt=0;
            col[i].fst=0;
            col[i].lst=0;
            col[i].cnt=0;
        }
    }
    bool ok()
    {
        for(ui i=1;i<=n;i++)
        {
            if(row[p[i].F].cnt>2) return false;
            if(col[p[i].S].cnt>2) return false;
            bool n=true,d=true;
            if(p[i].F>col[p[i].S].lst || p[i].F<col[p[i].S].fst) n=false;
            if(p[i].S>row[p[i].F].lst || p[i].S<row[p[i].F].fst) d=false;
            if(!n && !d) return false;
        }
        return true;
    }
    void Try()
    {
        if((ui)ans.size()>0) return ;
        for(ui i=1;i<=16;i++)
        {
            row[i].fst=0;
            row[i].lst=0;
            row[i].cnt=0;
            col[i].fst=0;
            col[i].lst=0;
            col[i].cnt=0;
        }
        for(ui i=1;i<=n;i++)
            if(bin[i])
            {
                row[p[i].F].cnt++;
                col[p[i].S].cnt++;
                if(row[p[i].F].fst==0 || row[p[i].F].fst>p[i].S) row[p[i].F].fst=p[i].S;
                if(row[p[i].F].lst<p[i].S) row[p[i].F].lst=p[i].S;
                if(col[p[i].S].fst==0 || col[p[i].S].fst>p[i].F) col[p[i].S].fst=p[i].F;
                if(col[p[i].S].lst<p[i].F) col[p[i].S].lst=p[i].F;
            }
        if(ok()) for(ui i=1;i<=n;i++) ans.pb(bin[i]);
    }
    void backtrack(ui pos)
    {
        if((ui)ans.size()>0) return ;
        for(ui i=0;i<2;i++)
        {
            bin[pos]=i;
            if(pos==n) Try();
            else backtrack(pos+1);
        }
    }
    void solve()
    {
        reset();
        backtrack(1);
    }
    void printAns()
    {
        for(ui i=0;i<(ui)ans.size();i++) cout<<ans[i];
        cout<<"\n";
    }
}
namespace Subtask_3
{
    bool check()
    {
        return true;
    }
    vector<ui> ans;
    pii high[N],low[N];
    bool on[N];
    void reset()
    {
        ans.clear();
        memset(high,0,sizeof high);
        memset(low,0,sizeof low);
        memset(on,false,sizeof on);
    }
    void solve()
    {
        for(ui i=1;i<=n;i++)
        {
            if(low[p[i].S].S==0) low[p[i].S]={i,p[i].F};
            else if(low[p[i].S].S>p[i].F) low[p[i].S]={i,p[i].F};
            if(high[p[i].S].S<p[i].F) high[p[i].S]={i,p[i].F};
        }
        for(ui i=1;i<=1000000;i++)
            if(high[i].S!=0 && low[i].S!=0)
            {
                on[high[i].F]=true;
                on[low[i].F]=true;
            }
        for(ui i=1;i<=n;i++) ans.pb(on[i]);
    }
    void printAns()
    {
        for(ui i=0;i<(ui)ans.size();i++) cout<<ans[i];
        cout<<"\n";
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    #ifdef CODE
    if(fopen(CODE".INP","r"))
    {
        freopen(CODE".INP","r",stdin);
        freopen(CODE".OUT","w",stdout);
    }
    #endif // CODE
    #define __FILE_CHECK__
    #ifdef __FILE_CHECK__
    if(fopen("inp.txt","r"))
    {
       freopen("inp.txt","r",stdin);
       freopen("out.txt","w",stdout);
       freopen("ans.txt","w",stderr);
    }
    #endif // __FILE_CHECK__
    cin>>n;
    for(ui i=1;i<=n;i++) cin>>p[i].F>>p[i].S;
    if(Subtask_2::check())
    {
        Subtask_2::solve();
        Subtask_2::printAns();
    }
    else
    {
        Subtask_3::solve();
        Subtask_3::printAns();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(CODE".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(CODE".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:162:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |        freopen("inp.txt","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:163:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |        freopen("out.txt","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:164:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |        freopen("ans.txt","w",stderr);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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