oj.uz

Submission #904630

# Submission time Handle Problem Language Result Execution time Memory
904630 2024-01-12T06:41:06 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 173220 KB 
#include <bits/stdc++.h>

#pragma optimize("03")
#pragma target("avx2")

using namespace std;

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

const int MAX=3e5+5;
const int B=224;
const int N=1e6;
const int block=450;
const int maxB=MAX/B+10;
const ll inf=1e18;  
const int mod=1e9+7;
const int mod1=1e9+9;
const int logg=15;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-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;
}

multiset<pii> pt;

void init(int R, int C, int sr, int sc, int M, char *s){
  pt.in({sr,sc});
  for(int i=0;i<M;i++){
    if(s[i]=='N')sr--;
    if(s[i]=='S')sr++;
    if(s[i]=='W')sc--;
    if(s[i]=='E')sc++;
    // cout<<sr<<" "<<sc<<"\n";
    pt.in({sr,sc});
  }
}

bool inthe(int ar, int br, int ac, int bc,pii x){
  return ar<=x.F&&x.F<=ac&&br<=x.S&&x.S<=bc;
}


set<pii> gr;
map<pii,int> mp;

void dfs(pii x){
  mp[x];
  for(int i=0;i<4;i++){
    int nx=x.F+dx[i],ny=x.S+dy[i];
    if(!mp.count({nx,ny})&&gr.count({nx,ny}))dfs({nx,ny});
  }
}

int colour(int ar, int br, int ac, int bc) {
  for(int i=ar-1;i<=ac+1;i++){
    pt.in({i,br-1});
    pt.in({i,bc+1});
  }
  for(int i=br-1;i<=bc+1;i++){
    pt.in({ar-1,i});
    pt.in({ac+1,i});
  }
  gr.clear();
  mp.clear();
  for(pii x:pt){
    for(int i=0;i<8;i++){
      int nx=x.F+dx[i],ny=x.S+dy[i];
      if(!pt.count({nx,ny})&&inthe(ar,br,ac,bc,{nx,ny})){
        gr.in({nx,ny});
      }
    }
  }
  int ans=0;
  for(pii x:gr){
    if(!mp.count(x)){
      dfs(x);
      ans++;
    }
  }
  for(int i=ar-1;i<=ac+1;i++){
    pt.erase(pt.find({i,br-1}));
    pt.erase(pt.find({i,bc+1}));
  }
  for(int i=br-1;i<=bc+1;i++){
    pt.erase(pt.find({ar-1,i}));
    pt.erase(pt.find({ac+1,i}));
  }
  return ans;
}

// int main(){
//   int r,c,m,q;
//   cin>>r>>c>>m>>q;
//   int sr,sc;
//   cin>>sr>>sc;
//   char s[MAX];
//   for(int i=0;i<m;i++)cin>>s[i];
//   init(r,c,sr,sc,m,s);
//   while(q--){
//     int ar,br,ac,bc;
//     cin>>ar>>br>>ac>>bc;
//     cout<<colour(ar,br,ac,bc)<<"\n";
//   }
// }

Compilation message

rainbow.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("03")
      | 
rainbow.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 448 KB Output is correct
2 Correct 694 ms 820 KB Output is correct
3 Correct 181 ms 496 KB Output is correct
4 Correct 257 ms 508 KB Output is correct
5 Correct 970 ms 852 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 505 ms 552 KB Output is correct
12 Correct 683 ms 564 KB Output is correct
13 Correct 825 ms 684 KB Output is correct
14 Correct 1560 ms 852 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1141 ms 81880 KB Output is correct
3 Correct 1158 ms 81728 KB Output is correct
4 Correct 1053 ms 77188 KB Output is correct
5 Correct 556 ms 38996 KB Output is correct
6 Correct 1588 ms 128796 KB Output is correct
7 Incorrect 2230 ms 173220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 448 KB Output is correct
2 Correct 694 ms 820 KB Output is correct
3 Correct 181 ms 496 KB Output is correct
4 Correct 257 ms 508 KB Output is correct
5 Correct 970 ms 852 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 505 ms 552 KB Output is correct
12 Correct 683 ms 564 KB Output is correct
13 Correct 825 ms 684 KB Output is correct
14 Correct 1560 ms 852 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3028 ms 11868 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 448 KB Output is correct
2 Correct 694 ms 820 KB Output is correct
3 Correct 181 ms 496 KB Output is correct
4 Correct 257 ms 508 KB Output is correct
5 Correct 970 ms 852 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 505 ms 552 KB Output is correct
12 Correct 683 ms 564 KB Output is correct
13 Correct 825 ms 684 KB Output is correct
14 Correct 1560 ms 852 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3028 ms 11868 KB Time limit exceeded
19 Halted 0 ms 0 KB -