oj.uz

Submission #1108340

# Submission time Handle Problem Language Result Execution time Memory
1108340 2024-11-03T21:33:41 Z Ludissey Mosaic (IOI24_mosaic) C++17
12 / 100
 1000 ms 1706844 KB 
#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

int q,n;
vector<vector<int>> lft;
vector<vector<int>>  top; 

vector<int> dia;
// X cest le top
// Y cest la gauche

// [le x][le y]

int todia(int x, int y){
  return (n-x-1)+y;
}

std::vector<long long> mosaic(std::vector<signed> X, std::vector<signed> Y, std::vector<signed> T, std::vector<signed> B,std::vector<signed> L, std::vector<signed> R) {
  q = sz(T); n=sz(Y);
  lft.resize(2,vector<int>(n,0));
  top.resize(n,vector<int>(2,0));
  dia.resize(n+n+4,0);
  for (int i = 0; i < n; i++)
  {
    lft[0][i]=Y[i];
    top[i][0]=X[i];
  }
  if(n>1){
    lft[1][0]=X[1];
    top[0][1]=Y[1];
  }
  for (int i = 1; i < n&&n>1; i++)
  {
    top[i][1]=(top[i-1][1]==0&&top[i][0]==0);
    lft[1][i]=(lft[1][i-1]==0&&lft[0][i]==0);
    dia[todia(i,1)]=top[i][1];
    dia[todia(1,i)]=lft[1][i];

  }
  
  vector<vector<int>> fullgrid(n,vector<int>(n,0));
  vector<vector<int>> fakegrid(n,vector<int>(n,0));
  vector<vector<int>> prefix(n,vector<int>(n,0));
  for (int i = 0; i < n; i++){
    for (int j = 0; j < min(n,2LL); j++)
    {
      fullgrid[i][j]=top[i][j];
      fullgrid[j][i]=lft[j][i];
    }
  }
  for (int i = 0; i < n; i++)
  {
    fakegrid[i][0]=X[i];
    fakegrid[0][i]=Y[i];
  }

  for (int i = 1; i < n; i++){
    for (int j = 1; j < n; j++)
    {
      fakegrid[i][j]=(fakegrid[i-1][j]==0&&fakegrid[i][j-1]==0);
    }
  }
  if(n>2){
    if(lft[1][2]==0&&top[2][1]==0){
      dia[todia(2,2)]=1;
    }
  }

  for (int i = n; i >= 2; i--)
  {
    if(dia[i]&&(i==2||dia[i-3]==0)) dia[i-2]=1;
  }
  for (int i = n; i <n+n-1; i++)
  {
    if(dia[i]&&dia[i+3]==0) dia[i+2]=1;
  }
  
  for (int i = 2; i < n; i++){
    for (int j = 2; j < n; j++)
    {
      fullgrid[i][j]=dia[todia(i,j)];
      fullgrid[j][i]=dia[todia(j,i)];
    }
  }
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++)
    {
      prefix[i][j]=fullgrid[i][j];
      if(i>0) prefix[i][j]+=prefix[i-1][j];
      if(j>0) prefix[i][j]+=prefix[i][j-1];
      if(i>0&&j>0) prefix[i][j]-=prefix[i-1][j-1];
      ////cerr << fullgrid[j][i] << " ";
    }
    ////cerr << "\n";
  }
  ////cerr<<"\n";
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++)
    {
      //cerr << fakegrid[j][i] << " ";
      //if(fakegrid[j][i]!=fullgrid[j][i]) cout << "ERROR - " << i << " " << j << "\n";
    }
    //cerr << "\n";
  }
  std::vector<long long> C(q, 0);
  for (int i = 0; i < q; i++)
  {
    int l=L[i],r=R[i],t=T[i],b=B[i];
    int sm=prefix[r][b];
    if(l>0) sm-=prefix[l-1][b];
    if(t>0) sm-=prefix[r][t-1];
    if(l>0&&t>0) sm+=prefix[l-1][t-1]; 
    C[i]=sm;
  }
  return C;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 2 ms 1360 KB Output is correct
13 Correct 2 ms 1360 KB Output is correct
14 Correct 2 ms 1360 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1230 ms 1613032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 2 ms 1360 KB Output is correct
13 Correct 2 ms 1360 KB Output is correct
14 Correct 2 ms 1360 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 771 ms 599892 KB Output is correct
19 Correct 708 ms 599880 KB Output is correct
20 Correct 714 ms 599676 KB Output is correct
21 Correct 729 ms 599624 KB Output is correct
22 Correct 698 ms 599624 KB Output is correct
23 Correct 168 ms 102772 KB Output is correct
24 Incorrect 155 ms 103240 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8264 KB Output is correct
2 Execution timed out 1192 ms 1706844 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1188 ms 1534508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1230 ms 1613032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 1360 KB Output is correct
13 Correct 2 ms 1360 KB Output is correct
14 Correct 2 ms 1360 KB Output is correct
15 Correct 2 ms 1360 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Execution timed out 1230 ms 1613032 KB Time limit exceeded
20 Halted 0 ms 0 KB -