Submission #1027808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027808		shenfe1	Tiles (BOI24_tiles)	C++17	19 / 100	29 ms	14932 KiB

Main

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast")

#define ll long long
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define int ll
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))

using namespace std;

const int MAX=2e5+15;
const ll inf=1e18;
const int mod=1e9+7;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

int binpow(int a,int n){
    if(!n)return 1;
    if(n%2==1)return a*binpow(a,n-1)%mod;
    int k=binpow(a,n/2);
    return k*k%mod;
}

int n,m;
int x[MAX],y[MAX];
vector<pii> vec[MAX];

void solve(){
    cin>>n>>m;
    set<int> st;
    map<int,int> mp;
    int cur=0;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        assert(y[i]<=1000);
        // y[i]/=2;
        // st.in(y[i]);
    }
    // for(int x:st){
    //     // while(cur%2!=x%2)cur++;
    //     mp[x]=cur++;
    // }
    // for(int i=1;i<=n;i++){
    //     y[i]=mp[y[i]];
    // }

    for(int i=1;i<=n;i++){
        int nx=x[i%n+1],ny=y[i%n+1];
        if(nx==x[i]){
            vec[x[i]].pb({min(ny,y[i]),max(ny,y[i])-1});
        }
    }
    int ans=0;
    // T.init();
    vector<int> use(MAX,0),push(MAX,0);
    for(int i=0;i<m;i++){
        for(auto [l,r]:vec[i]){
            int sum=0;
            for(int j=l;j<=r;j++){
                sum+=use[j];
                use[j]^=1;
            }
            assert(sum==0||sum==r-l+1);
        }
        int sum=0;
        for(int j=0;j<=1000;j++){
            if(push[j]){
                if(!use[j]){
                    cout<<ans<<"\n";
                    return;
                }
                else{
                    push[j]=0;
                }
            }
            else{
                if(use[j]){
                    push[j]=1;
                }
            }
            sum+=push[j];
        }
        for(int j=0;j<=1000;){
            if(push[j]){
                if(push[j+1])j+=2;
                else{
                    cout<<ans<<"\n";
                    return;
                }
            }
            else j++;
        }
        if(!sum)ans=max(ans,i+1);
        // assert(ans<=m);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}   

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:45:9: warning: unused variable 'cur' [-Wunused-variable]
   45 |     int cur=0;
      |         ^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 19 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10