oj.uz

Submission #832610

# Submission time Handle Problem Language Result Execution time Memory
832610 2023-08-21T12:35:08 Z 8pete8 Towers (NOI22_towers) C++17
29 / 100
 419 ms 137116 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(x[xx].size()==1){
        if(cy[x[xx][0].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][0].f]<xx){
            int nx=cy[x[xx][0].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);
            }
        }
        }
        return;
    }
    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;
        if(x[i].size()==1){
            update(i,1);
            continue;
        }
        update(i,1);
        update(i,0);
    }
    cout<<ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70716 KB Output is correct
2 Correct 33 ms 70664 KB Output is correct
3 Correct 33 ms 70636 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 34 ms 70700 KB Output is correct
6 Correct 33 ms 70736 KB Output is correct
7 Correct 32 ms 70768 KB Output is correct
8 Correct 32 ms 70672 KB Output is correct
9 Correct 32 ms 70648 KB Output is correct
10 Correct 33 ms 70716 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70716 KB Output is correct
2 Correct 33 ms 70664 KB Output is correct
3 Correct 33 ms 70636 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 34 ms 70700 KB Output is correct
6 Correct 33 ms 70736 KB Output is correct
7 Correct 32 ms 70768 KB Output is correct
8 Correct 32 ms 70672 KB Output is correct
9 Correct 32 ms 70648 KB Output is correct
10 Correct 33 ms 70716 KB Output is correct
11 Correct 32 ms 70732 KB Output is correct
12 Correct 32 ms 70696 KB Output is correct
13 Correct 32 ms 70700 KB Output is correct
14 Correct 33 ms 70740 KB Output is correct
15 Correct 38 ms 70700 KB Output is correct
16 Correct 35 ms 70740 KB Output is correct
17 Correct 39 ms 70720 KB Output is correct
18 Correct 33 ms 70652 KB Output is correct
19 Correct 33 ms 70648 KB Output is correct
20 Correct 33 ms 70716 KB Output is correct
21 Correct 33 ms 70684 KB Output is correct
22 Correct 33 ms 70756 KB Output is correct
23 Correct 33 ms 70720 KB Output is correct
24 Correct 33 ms 70768 KB Output is correct
25 Correct 33 ms 70760 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75324 KB Output is correct
2 Correct 53 ms 76084 KB Output is correct
3 Correct 90 ms 85868 KB Output is correct
4 Correct 147 ms 102280 KB Output is correct
5 Correct 54 ms 77032 KB Output is correct
6 Correct 38 ms 72128 KB Output is correct
7 Correct 130 ms 98244 KB Output is correct
8 Correct 107 ms 91196 KB Output is correct
9 Correct 182 ms 110612 KB Output is correct
10 Correct 157 ms 105096 KB Output is correct
11 Correct 198 ms 112200 KB Output is correct
12 Correct 205 ms 112164 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 123560 KB Output is correct
2 Correct 394 ms 136008 KB Output is correct
3 Correct 407 ms 136092 KB Output is correct
4 Correct 406 ms 136020 KB Output is correct
5 Correct 389 ms 136092 KB Output is correct
6 Correct 390 ms 137028 KB Output is correct
7 Correct 415 ms 137032 KB Output is correct
8 Correct 407 ms 137032 KB Output is correct
9 Correct 404 ms 137116 KB Output is correct
10 Correct 397 ms 136992 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70716 KB Output is correct
2 Correct 33 ms 70664 KB Output is correct
3 Correct 33 ms 70636 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 34 ms 70700 KB Output is correct
6 Correct 33 ms 70736 KB Output is correct
7 Correct 32 ms 70768 KB Output is correct
8 Correct 32 ms 70672 KB Output is correct
9 Correct 32 ms 70648 KB Output is correct
10 Correct 33 ms 70716 KB Output is correct
11 Correct 32 ms 70732 KB Output is correct
12 Correct 32 ms 70696 KB Output is correct
13 Correct 32 ms 70700 KB Output is correct
14 Correct 33 ms 70740 KB Output is correct
15 Correct 38 ms 70700 KB Output is correct
16 Correct 35 ms 70740 KB Output is correct
17 Correct 39 ms 70720 KB Output is correct
18 Correct 33 ms 70652 KB Output is correct
19 Correct 33 ms 70648 KB Output is correct
20 Correct 33 ms 70716 KB Output is correct
21 Correct 33 ms 70684 KB Output is correct
22 Correct 33 ms 70756 KB Output is correct
23 Correct 33 ms 70720 KB Output is correct
24 Correct 33 ms 70768 KB Output is correct
25 Correct 33 ms 70760 KB Output is correct
26 Correct 35 ms 71032 KB Output is correct
27 Correct 34 ms 71108 KB Output is correct
28 Incorrect 38 ms 71012 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70716 KB Output is correct
2 Correct 33 ms 70664 KB Output is correct
3 Correct 33 ms 70636 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 34 ms 70700 KB Output is correct
6 Correct 33 ms 70736 KB Output is correct
7 Correct 32 ms 70768 KB Output is correct
8 Correct 32 ms 70672 KB Output is correct
9 Correct 32 ms 70648 KB Output is correct
10 Correct 33 ms 70716 KB Output is correct
11 Correct 32 ms 70732 KB Output is correct
12 Correct 32 ms 70696 KB Output is correct
13 Correct 32 ms 70700 KB Output is correct
14 Correct 33 ms 70740 KB Output is correct
15 Correct 38 ms 70700 KB Output is correct
16 Correct 35 ms 70740 KB Output is correct
17 Correct 39 ms 70720 KB Output is correct
18 Correct 33 ms 70652 KB Output is correct
19 Correct 33 ms 70648 KB Output is correct
20 Correct 33 ms 70716 KB Output is correct
21 Correct 33 ms 70684 KB Output is correct
22 Correct 33 ms 70756 KB Output is correct
23 Correct 33 ms 70720 KB Output is correct
24 Correct 33 ms 70768 KB Output is correct
25 Correct 33 ms 70760 KB Output is correct
26 Correct 35 ms 71032 KB Output is correct
27 Correct 34 ms 71108 KB Output is correct
28 Incorrect 38 ms 71012 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70716 KB Output is correct
2 Correct 33 ms 70664 KB Output is correct
3 Correct 33 ms 70636 KB Output is correct
4 Correct 34 ms 70732 KB Output is correct
5 Correct 34 ms 70700 KB Output is correct
6 Correct 33 ms 70736 KB Output is correct
7 Correct 32 ms 70768 KB Output is correct
8 Correct 32 ms 70672 KB Output is correct
9 Correct 32 ms 70648 KB Output is correct
10 Correct 33 ms 70716 KB Output is correct
11 Correct 32 ms 70732 KB Output is correct
12 Correct 32 ms 70696 KB Output is correct
13 Correct 32 ms 70700 KB Output is correct
14 Correct 33 ms 70740 KB Output is correct
15 Correct 38 ms 70700 KB Output is correct
16 Correct 35 ms 70740 KB Output is correct
17 Correct 39 ms 70720 KB Output is correct
18 Correct 33 ms 70652 KB Output is correct
19 Correct 33 ms 70648 KB Output is correct
20 Correct 33 ms 70716 KB Output is correct
21 Correct 33 ms 70684 KB Output is correct
22 Correct 33 ms 70756 KB Output is correct
23 Correct 33 ms 70720 KB Output is correct
24 Correct 33 ms 70768 KB Output is correct
25 Correct 33 ms 70760 KB Output is correct
26 Correct 45 ms 75324 KB Output is correct
27 Correct 53 ms 76084 KB Output is correct
28 Correct 90 ms 85868 KB Output is correct
29 Correct 147 ms 102280 KB Output is correct
30 Correct 54 ms 77032 KB Output is correct
31 Correct 38 ms 72128 KB Output is correct
32 Correct 130 ms 98244 KB Output is correct
33 Correct 107 ms 91196 KB Output is correct
34 Correct 182 ms 110612 KB Output is correct
35 Correct 157 ms 105096 KB Output is correct
36 Correct 198 ms 112200 KB Output is correct
37 Correct 205 ms 112164 KB Output is correct
38 Correct 419 ms 123560 KB Output is correct
39 Correct 394 ms 136008 KB Output is correct
40 Correct 407 ms 136092 KB Output is correct
41 Correct 406 ms 136020 KB Output is correct
42 Correct 389 ms 136092 KB Output is correct
43 Correct 390 ms 137028 KB Output is correct
44 Correct 415 ms 137032 KB Output is correct
45 Correct 407 ms 137032 KB Output is correct
46 Correct 404 ms 137116 KB Output is correct
47 Correct 397 ms 136992 KB Output is correct
48 Correct 35 ms 71032 KB Output is correct
49 Correct 34 ms 71108 KB Output is correct
50 Incorrect 38 ms 71012 KB Output isn't correct
51 Halted 0 ms 0 KB -