oj.uz

Submission #544968

# Submission time Handle Problem Language Result Execution time Memory
544968 2022-04-03T08:51:39 Z zaneyu Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 14804 KB 
#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("O2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
vector<int> v[maxn],v2[maxn];
vector<int> bad[maxn];
int l=INF,r=0;
bool vis[2005][2005];
bool ok[2005][2005];
int n,m;
void init(int N, int C, int x, int y, int M, char *S) {
    //v[x].pb(y);
    n=N,m=C;
    MNTO(l,y),MXTO(r,y);
    ok[x][y]=1;
    REP(i,M){
        if(S[i]=='N') --x;
        else if(S[i]=='S') ++x;
        else if(S[i]=='E') ++y;
        else --y;
        //v[x].pb(y);
        MNTO(l,y),MXTO(r,y);
        ok[x][y]=1;
    }
    /*
    REP1(i,n){
        SORT_UNIQUE(v[i]);
        bad[i]=v[i];
        vector<int> vv;
        REP(j,sz(v[i])){
            int p=j;
            while(j<sz(v[i]) and v[i][j]-v[i][p]==j-p) ++j;
            --j;
            v2[i].pb(v[i][j]);
            vv.pb(v[i][p]);
        }
        //cout<<vv<<'\n';
        v[i]=vv;
    }*/
}
bool is(int x,int y){
    return ok[x][y];
}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int colour(int ar, int ac, int br, int bc) {
    int cnt=0;
    for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            if(!vis[i][j] and !is(i,j)){
                vis[i][j]=1;
                queue<pii> q;
                q.push({i,j});
                while(sz(q)){
                    pii z=q.front();
                    q.pop();
                    REP(k,4){
                        int x=z.f+dx[k],y=z.s+dy[k];
                        if(x<ar or x>br or y<ac or y>bc or is(x,y) or vis[x][y]) continue;
                        vis[x][y]=1;
                        q.push({x,y});
                    }
                }
                //cout<<i<<' '<<j<<'\n';
                ++cnt;
            }
        }
        //cout<<ans<<' ';
    }
for(int i=ar;i<=br;i++){
        for(int j=ac;j<=bc;j++){
            vis[i][j]=0;
        }
    }
    return cnt;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 10 ms 7508 KB Output is correct
3 Correct 24 ms 7508 KB Output is correct
4 Correct 18 ms 7588 KB Output is correct
5 Correct 9 ms 7592 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7360 KB Output is correct
8 Correct 4 ms 7360 KB Output is correct
9 Correct 4 ms 7360 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 17 ms 7572 KB Output is correct
12 Correct 14 ms 7596 KB Output is correct
13 Correct 12 ms 7596 KB Output is correct
14 Correct 14 ms 7600 KB Output is correct
15 Correct 3 ms 7252 KB Output is correct
16 Correct 3 ms 7252 KB Output is correct
17 Correct 3 ms 7252 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Execution timed out 3057 ms 7676 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Runtime error 10 ms 14804 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 10 ms 7508 KB Output is correct
3 Correct 24 ms 7508 KB Output is correct
4 Correct 18 ms 7588 KB Output is correct
5 Correct 9 ms 7592 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7360 KB Output is correct
8 Correct 4 ms 7360 KB Output is correct
9 Correct 4 ms 7360 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 17 ms 7572 KB Output is correct
12 Correct 14 ms 7596 KB Output is correct
13 Correct 12 ms 7596 KB Output is correct
14 Correct 14 ms 7600 KB Output is correct
15 Correct 3 ms 7252 KB Output is correct
16 Correct 3 ms 7252 KB Output is correct
17 Correct 3 ms 7252 KB Output is correct
18 Execution timed out 3075 ms 11740 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 10 ms 7508 KB Output is correct
3 Correct 24 ms 7508 KB Output is correct
4 Correct 18 ms 7588 KB Output is correct
5 Correct 9 ms 7592 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7360 KB Output is correct
8 Correct 4 ms 7360 KB Output is correct
9 Correct 4 ms 7360 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 17 ms 7572 KB Output is correct
12 Correct 14 ms 7596 KB Output is correct
13 Correct 12 ms 7596 KB Output is correct
14 Correct 14 ms 7600 KB Output is correct
15 Correct 3 ms 7252 KB Output is correct
16 Correct 3 ms 7252 KB Output is correct
17 Correct 3 ms 7252 KB Output is correct
18 Execution timed out 3075 ms 11740 KB Time limit exceeded
19 Halted 0 ms 0 KB -