oj.uz

Submission #832598

# Submission time Handle Problem Language Result Execution time Memory
832598 2023-08-21T12:16:12 Z 8pete8 Towers (NOI22_towers) C++17
7 / 100
 380 ms 123608 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define mod 9871
const int mxn=1e6,inf=1e7;
vector<pii>x[mxn+10];
vector<pii>y[mxn+10];
pii cx[mxn+10];
int cy[mxn+10];
string ans="";
void update(int xx,int di){
    bool yes=true;
    if(di){
        while(cx[xx].f<cx[xx].s){
            yes=true;
            if(cy[x[xx][cx[xx].f].f]==-1){
                ans[x[xx][cx[xx].f].s]='1';
                cy[x[xx][cx[xx].f].f]=0;
            }
            else{
                if(cy[x[xx][cx[xx].f].f]==0)cy[x[xx][cx[xx].f].f]=xx,ans[x[xx][cx[xx].f].s]='1';
                else if(cy[x[xx][cx[xx].f].f]<xx){
                    int nx=cy[x[xx][cx[xx].f].f];
                    if(x[nx][cx[nx].f].f==x[xx][cx[xx].f].f){
                        cy[x[xx][cx[xx].f].f]=xx;
                        ans[x[nx][cx[nx].f].s]='0';
                        ans[x[xx][cx[xx].f].s]='1';
                        update(nx,1);
                    }
                    else if(x[nx][cx[nx].s].f==x[xx][cx[xx].f].f){
                        cy[x[xx][cx[xx].f].f]=xx;
                        ans[x[nx][cx[nx].s].s]='0';
                        ans[x[xx][cx[xx].f].s]='1';
                        update(nx,0);
                    }
                    
                }
                else cx[xx].f++,yes=false;;
            }
            if(yes)break;
        }
        return;
    }
    while(cx[xx].f<cx[xx].s){
        yes=true;
        if(cy[x[xx][cx[xx].s].f]==-1){
            ans[x[xx][cx[xx].s].s]='1';
            cy[x[xx][cx[xx].s].f]=0;
        }
        else{
            if(cy[x[xx][cx[xx].s].f]==0)cy[x[xx][cx[xx].s].f]=xx,ans[x[xx][cx[xx].s].s]='1';
            else if(cy[x[xx][cx[xx].s].f]<xx){
                int nx=cy[x[xx][cx[xx].s].f];
                if(x[nx][cx[nx].f].f==x[xx][cx[xx].s].f){
                    cy[x[xx][cx[xx].s].f]=xx;
                    ans[x[nx][cx[nx].f].s]='0';
                    ans[x[xx][cx[xx].s].s]='1';
                    update(nx,1);
                }
                else if(x[nx][cx[nx].s].f==x[xx][cx[xx].s].f){
                    cy[x[xx][cx[xx].s].f]=xx;
                    ans[x[nx][cx[nx].s].s]='0';
                    ans[x[xx][cx[xx].s].s]='1';
                    update(nx,0);
                }
            }
            else cx[xx].s--,yes=false;;
        }
        if(yes)break;
        }
}
int32_t main(){
    fastio
    int n;cin>>n;
    vector<ppii>v(n);
    for(int i=0;i<n;i++)ans+='0';
    for(int i=0;i<n;i++)cin>>v[i].f.f>>v[i].f.s,v[i].s=i;
    sort(v.begin(),v.end());
    for(auto i:v)x[i.f.f].pb({i.f.s,i.s});
    for(int i=0;i<=mxn;i++)cx[i]={-1,-1},cy[i]=-1;
    for(int i=1;i<=mxn;i++){
        if(x[i].size()==0)continue;
        cx[i].f=0;
        cx[i].s=x[i].size()-1;
        update(i,1);
        update(i,0);
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 75372 KB Output is correct
2 Correct 53 ms 76864 KB Output is correct
3 Correct 92 ms 88360 KB Output is correct
4 Correct 147 ms 107356 KB Output is correct
5 Correct 60 ms 77900 KB Output is correct
6 Correct 39 ms 72280 KB Output is correct
7 Correct 130 ms 103224 KB Output is correct
8 Correct 103 ms 94344 KB Output is correct
9 Correct 182 ms 118324 KB Output is correct
10 Correct 154 ms 111344 KB Output is correct
11 Correct 199 ms 119920 KB Output is correct
12 Correct 193 ms 119832 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 123608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -