oj.uz

답안 #408690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
408690 2021-05-19T13:38:56 Z MKopchev 자리 배치 (IOI18_seats) C++14
100 / 100
 2473 ms 180744 KB 
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

const int nmax=1e6+42;

int n,m;

pair<int,int> where[nmax];

vector< vector<int> > inp;

pair<int,int> cnt[nmax];

struct info
{
    pair<int,int> mini;
    pair<int,int> sum;
    int cnt_mini;
};

void print(string s,info a)
{
    cout<<s<<" -> ";cout<<a.mini.first<<" "<<a.mini.second<<" , "<<a.sum.first<<" "<<a.sum.second<<" , "<<a.cnt_mini<<endl;
}
info tree[4*nmax];

info my_merge(info a,info b)
{
    b.mini={b.mini.first+a.sum.first,b.mini.second+a.sum.second};

    if(a.mini==b.mini)
    {
        a.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
        a.cnt_mini+=b.cnt_mini;

        return a;
    }

    if(a.mini>b.mini)swap(a,b);

    a.sum={a.sum.first+b.sum.first,a.sum.second+b.sum.second};
    return a;
}
void update(int node,int l,int r,int pos,pair<int,int> val)
{
    if(l==r)
    {
        tree[node].mini=val;
        tree[node].sum=val;
        tree[node].cnt_mini=1;

        //cout<<"pos= "<<pos<<" node= "<<node;print(" tree",tree[node]);

        return;
    }

    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);

    /*
    cout<<"node= "<<node<<" l= "<<l<<" r= "<<r<<endl;

    print("tree[node*2]",tree[node*2]);
    print("tree[node*2+1]",tree[node*2+1]);
    print("tree[node]",tree[node]);

    cout<<"---"<<endl;
    */
}

int ask(int x,int y)
{
    if(0>x||x>=n||0>y||y>=m)return 1e9;
    return inp[x][y];
}

void eval(int x,int y)
{
    if(0>x||x>=n||0>y||y>=m)return;

    int cur[5]={0,0,0,0,0};

    int help;

    help=1+(ask(x-1,y-1)<inp[x][y])+(ask(x-1,y)<inp[x][y])+(ask(x,y-1)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x-1,y)<inp[x][y])+(ask(x-1,y+1)<inp[x][y])+(ask(x,y+1)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x,y-1)<inp[x][y])+(ask(x+1,y-1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x,y+1)<inp[x][y])+(ask(x+1,y+1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
    cur[help]++;

    cnt[inp[x][y]]={cur[1]-cur[2],cur[3]-cur[4]};

    update(1,0,n*m-1,inp[x][y],cnt[inp[x][y]]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    for(int i=0;i<4*nmax;i++)
    {
        tree[i].mini={10,10};
        tree[i].sum={10,10};
    }

    n=H;
    m=W;

    for(int t=0;t<n*m;t++)
    {
        int i=R[t];
        int j=C[t];

        while(inp.size()<=i)inp.push_back({});
        while(inp[i].size()<=j)inp[i].push_back(j);

        where[t]={i,j};
        inp[i][j]=t;
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            eval(i,j);
}

int swap_seats(int a, int b)
{
    swap(inp[where[a].first][where[a].second],inp[where[b].first][where[b].second]);
    swap(where[a],where[b]);

    for(int x=-1;x<=1;x++)
        for(int y=-1;y<=1;y++)
        {
            eval(where[a].first+x,where[a].second+y);
            eval(where[b].first+x,where[b].second+y);
        }

    //print("tree[1]",tree[1]);

    return tree[1].cnt_mini;
}
/*
int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}
*/

Compilation message

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:135:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |         while(inp.size()<=i)inp.push_back({});
      |               ~~~~~~~~~~^~~
seats.cpp:136:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |         while(inp[i].size()<=j)inp[i].push_back(j);
      |               ~~~~~~~~~~~~~^~~
seats.cpp: At global scope:
seats.cpp:7:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
    7 | int read_int() {
      |     ^~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 78788 KB Output is correct
2 Correct 66 ms 78624 KB Output is correct
3 Correct 72 ms 78644 KB Output is correct
4 Correct 67 ms 78612 KB Output is correct
5 Correct 59 ms 78652 KB Output is correct
6 Correct 67 ms 78692 KB Output is correct
7 Correct 70 ms 78660 KB Output is correct
8 Correct 70 ms 78628 KB Output is correct
9 Correct 70 ms 78580 KB Output is correct
10 Correct 69 ms 78656 KB Output is correct
11 Correct 67 ms 78600 KB Output is correct
12 Correct 60 ms 78636 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 78788 KB Output is correct
2 Correct 66 ms 78624 KB Output is correct
3 Correct 72 ms 78644 KB Output is correct
4 Correct 67 ms 78612 KB Output is correct
5 Correct 59 ms 78652 KB Output is correct
6 Correct 67 ms 78692 KB Output is correct
7 Correct 70 ms 78660 KB Output is correct
8 Correct 70 ms 78628 KB Output is correct
9 Correct 70 ms 78580 KB Output is correct
10 Correct 69 ms 78656 KB Output is correct
11 Correct 67 ms 78600 KB Output is correct
12 Correct 60 ms 78636 KB Output is correct
13 Correct 103 ms 79036 KB Output is correct
14 Correct 105 ms 78988 KB Output is correct
15 Correct 76 ms 79044 KB Output is correct
16 Correct 73 ms 79456 KB Output is correct
17 Correct 88 ms 79044 KB Output is correct
18 Correct 102 ms 78908 KB Output is correct
19 Correct 98 ms 79024 KB Output is correct
20 Correct 87 ms 79148 KB Output is correct
21 Correct 80 ms 79048 KB Output is correct
22 Correct 74 ms 79492 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1510 ms 114244 KB Output is correct
2 Correct 1148 ms 130312 KB Output is correct
3 Correct 1185 ms 129832 KB Output is correct
4 Correct 1075 ms 129912 KB Output is correct
5 Correct 1056 ms 130212 KB Output is correct
6 Correct 1062 ms 129860 KB Output is correct
7 Correct 1090 ms 129908 KB Output is correct
8 Correct 1136 ms 129944 KB Output is correct
9 Correct 1141 ms 129972 KB Output is correct
10 Correct 1082 ms 129968 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 79004 KB Output is correct
2 Correct 184 ms 82104 KB Output is correct
3 Correct 1020 ms 113936 KB Output is correct
4 Correct 1482 ms 130196 KB Output is correct
5 Correct 961 ms 129908 KB Output is correct
6 Correct 1722 ms 180744 KB Output is correct
7 Correct 1010 ms 129972 KB Output is correct
8 Correct 1194 ms 131828 KB Output is correct
9 Correct 1093 ms 131456 KB Output is correct
10 Correct 1089 ms 136160 KB Output is correct
11 Correct 1047 ms 153340 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 79604 KB Output is correct
2 Correct 108 ms 79560 KB Output is correct
3 Correct 143 ms 79612 KB Output is correct
4 Correct 171 ms 79556 KB Output is correct
5 Correct 221 ms 79816 KB Output is correct
6 Correct 1249 ms 114280 KB Output is correct
7 Correct 1293 ms 130984 KB Output is correct
8 Correct 1239 ms 131088 KB Output is correct
9 Correct 1737 ms 130920 KB Output is correct
10 Correct 1188 ms 131052 KB Output is correct
11 Correct 1180 ms 130896 KB Output is correct
12 Correct 1196 ms 130920 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 78788 KB Output is correct
2 Correct 66 ms 78624 KB Output is correct
3 Correct 72 ms 78644 KB Output is correct
4 Correct 67 ms 78612 KB Output is correct
5 Correct 59 ms 78652 KB Output is correct
6 Correct 67 ms 78692 KB Output is correct
7 Correct 70 ms 78660 KB Output is correct
8 Correct 70 ms 78628 KB Output is correct
9 Correct 70 ms 78580 KB Output is correct
10 Correct 69 ms 78656 KB Output is correct
11 Correct 67 ms 78600 KB Output is correct
12 Correct 60 ms 78636 KB Output is correct
13 Correct 103 ms 79036 KB Output is correct
14 Correct 105 ms 78988 KB Output is correct
15 Correct 76 ms 79044 KB Output is correct
16 Correct 73 ms 79456 KB Output is correct
17 Correct 88 ms 79044 KB Output is correct
18 Correct 102 ms 78908 KB Output is correct
19 Correct 98 ms 79024 KB Output is correct
20 Correct 87 ms 79148 KB Output is correct
21 Correct 80 ms 79048 KB Output is correct
22 Correct 74 ms 79492 KB Output is correct
23 Correct 1510 ms 114244 KB Output is correct
24 Correct 1148 ms 130312 KB Output is correct
25 Correct 1185 ms 129832 KB Output is correct
26 Correct 1075 ms 129912 KB Output is correct
27 Correct 1056 ms 130212 KB Output is correct
28 Correct 1062 ms 129860 KB Output is correct
29 Correct 1090 ms 129908 KB Output is correct
30 Correct 1136 ms 129944 KB Output is correct
31 Correct 1141 ms 129972 KB Output is correct
32 Correct 1082 ms 129968 KB Output is correct
33 Correct 104 ms 79004 KB Output is correct
34 Correct 184 ms 82104 KB Output is correct
35 Correct 1020 ms 113936 KB Output is correct
36 Correct 1482 ms 130196 KB Output is correct
37 Correct 961 ms 129908 KB Output is correct
38 Correct 1722 ms 180744 KB Output is correct
39 Correct 1010 ms 129972 KB Output is correct
40 Correct 1194 ms 131828 KB Output is correct
41 Correct 1093 ms 131456 KB Output is correct
42 Correct 1089 ms 136160 KB Output is correct
43 Correct 1047 ms 153340 KB Output is correct
44 Correct 91 ms 79604 KB Output is correct
45 Correct 108 ms 79560 KB Output is correct
46 Correct 143 ms 79612 KB Output is correct
47 Correct 171 ms 79556 KB Output is correct
48 Correct 221 ms 79816 KB Output is correct
49 Correct 1249 ms 114280 KB Output is correct
50 Correct 1293 ms 130984 KB Output is correct
51 Correct 1239 ms 131088 KB Output is correct
52 Correct 1737 ms 130920 KB Output is correct
53 Correct 1188 ms 131052 KB Output is correct
54 Correct 1180 ms 130896 KB Output is correct
55 Correct 1196 ms 130920 KB Output is correct
56 Correct 153 ms 80248 KB Output is correct
57 Correct 274 ms 80196 KB Output is correct
58 Correct 506 ms 80636 KB Output is correct
59 Correct 1860 ms 131028 KB Output is correct
60 Correct 2473 ms 131184 KB Output is correct
61 Correct 1715 ms 130940 KB Output is correct
62 Correct 1400 ms 130996 KB Output is correct
63 Correct 2151 ms 131116 KB Output is correct
64 Correct 1779 ms 131032 KB Output is correct
65 Correct 1840 ms 132732 KB Output is correct
66 Correct 1865 ms 132360 KB Output is correct
67 Correct 1769 ms 137240 KB Output is correct
68 Correct 1534 ms 145064 KB Output is correct
69 Correct 2313 ms 154364 KB Output is correct