Submission #38148

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
38148	2018-01-02 11:44:30	14kg	Weighting stones (IZhO11_stones)	C++11	100 / 100	63 ms	7256 KiB

stones

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <algorithm>
#define min2(x,y) (x<y?x:y)
using namespace std;
int n, nn;
pair<int, int> tree[3][262144];
int cnt[3], MAX[3];
void Update(int x, int y) {
  tree[x][y] = { tree[x][y * 2].first + tree[x][y * 2 + 1].first - min2(tree[x][y * 2].first,tree[x][y * 2 + 1].second),
    tree[x][y * 2].second + tree[x][y * 2 + 1].second - min2(tree[x][y * 2].first,tree[x][y * 2 + 1].second) };
  if (y > 1) Update(x, y / 2);
}
int main() {
  int x, w;
  scanf("%d", &n);
  for (nn = 1; nn < n; nn *= 2);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &x, &w);
    cnt[w]++, MAX[w] = MAX[w] > x ? MAX[w] : x;
    tree[w][nn + x - 1] = { 0,1 }, Update(w, (nn + x - 1) / 2);
    tree[3 - w][nn + x - 1] = { 1,0 }, Update(3 - w, (nn + x - 1) / 2);
    
    if ((cnt[1]<cnt[2] && MAX[1]>MAX[2]) || (cnt[1]>cnt[2] && MAX[1]<MAX[2])) {
      printf("?\n");
      continue;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

stones.cpp: In function 'int main()':
stones.cpp:18:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
stones.cpp:21:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &w);
                         ^

• Subtask 1: 100 / 100