oj.uz

Submission #1027805

# Submission time Handle Problem Language Result Execution time Memory
1027805 2024-07-19T10:10:42 Z shenfe1 Tiles (BOI24_tiles) C++17
0 / 100
 26 ms 13148 KB 
#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+2;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);
    }
    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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Runtime error 5 ms 10076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Runtime error 5 ms 10076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Runtime error 6 ms 10180 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 26 ms 13148 KB Output is correct
6 Correct 20 ms 13148 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct
9 Correct 4 ms 8284 KB Output is correct
10 Incorrect 5 ms 8540 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10072 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10072 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Runtime error 5 ms 10076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -