Submission #1109272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109272	2024-11-06T10:06:48 Z	Kerim	Mosaic (IOI24_mosaic)	C++17	Compilation error	0 ms	0 KB

mosaic

#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int N = 4e5+5;
int cnt[N], arcalyk[4][N], tarhun[N][4];
ll pre[N], suf[N], cep[N], sag[N];
const int M = 5005;
int dp[M][M];
int wow(int a, int b){
    return (!(a|b)?1:0);
}

vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
    int n = (int)X.size();
    for (int i = 0; i < n+n; i++)
        cnt[i] = 0;
    map<pii, int> mp;
    for(int i = 1; i <= n; ++i)
        mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1];
    for(int i = 2; i <= n; ++i)
        for(int j = 2; j <= 3; ++j)
            mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
    for(int i = 2; i <= 3; ++i)
        for(int j = 2; j <= n; ++j)
            mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);

    int i = 3;
    for(int j = 3; j <= n; ++j)
        cnt[i-j+n] = mp[{i, j}];
    int j = 3;
    for(int i = 3; i <= n; ++i)
        cnt[i-j+n] = mp[{i, j}];

    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1];
    for (int j = 1; j <= 3; j++)
        for (int i = 1; i <= n; i++)
            tarhun[i][j] = mp[{i,j}] + tarhun[i-1][j];

    suf[n+n] = cep[n+n] = 0;
    sag[0] = pre[0] = cnt[0];
    for (int i = 1; i < n+n; i++){
        pre[i] = pre[i-1] + cnt[i];
        sag[i] = sag[i-1] + pre[i-1] + cnt[i];
    }
    for (int i = n+n-1; i >= 0; i--){
        suf[i] = suf[i+1] + cnt[i];
        cep[i] = cep[i+1] + suf[i+1] + cnt[i];
    }

    vector<ll> ans;
    for(int i = 0; i < (int)L.size(); ++i){
        int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
        ll res = 0;
        while (x <= 3 and x <= xx)
            res += arcalyk[x][yy]-arcalyk[x][y-1], x += 1;
        if (x <= xx){
            while (y <= 3 and y <= yy)
                res += tarhun[xx][y]-tarhun[x-1][y], y += 1;
        }
        if (x <= xx and y <= yy){
            int a = x-y+n, b = x-yy+n, k = xx-x+1;
            swap(a, b);
            int len = b-a+1;
            b += k-1;
            k = min(k, len);
            res += cep[a] - (cep[a+k]+k*suf[a+k]);
            res += sag[b] - (sag[b-k]+k*pre[b-k]);

            // for (int j = 0; j < k; j++){
                // res += cnt[a++] * 1LL * (j+1);
                // res += cnt[b--] * 1LL * (j+1);
            // }
            a += k; b -= k;
            if (a > b)
                res -= cnt[++b] * 1LL * k;
            res += (pre[b]-pre[a-1])*1LL*k;
        }
        ans.pb(res);
    }
    return ans;
}

int main(){
    freopen("file.in", "r", stdin);
    srand((unsigned)time(NULL));
    // while (1){
        int n = rand()%10+2;
        scanf("%d", &n);
        vector<int> X, Y;
        for(int i = 1; i <= n; ++i){
            int x = rand()%2;
            scanf("%d", &x);
            X.pb(x);
        }
        for(int i = 1; i <= n; ++i){
            int x = rand()%2;
            scanf("%d", &x);
            Y.pb(x);
        }
        Y[0] = X[0];
        int q = 1000;
        scanf("%d", &q);
        vector<int> T, B, L, R;
        while(q--){
            int a = rand()%n, b = rand()%n, c = rand()%n, d = rand()%n;
            scanf("%d%d%d%d", &a, &b, &c, &d);
            if (a > b) swap(a, b);
            if (c > d) swap(c, d);
            T.pb(a), B.pb(b), L.pb(c), R.pb(d);
        }
        vector<ll> ans = mosaic(X, Y, T, B, L, R);
        for(ll i : ans)
            printf("%lld ", i);
        puts("");
    // }
    return 0;
}

Compilation message

mosaic.cpp: In function 'int main()':
mosaic.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("file.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mosaic.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
mosaic.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
mosaic.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
mosaic.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
mosaic.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |             scanf("%d%d%d%d", &a, &b, &c, &d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc3wgvAV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccL2EYyW.o:mosaic.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status