Блог пользователя LLI_E_P_JI_O_K

Некорректная работа оптимизатора Microsoft Visual C++ 2010
Автор LLI_E_P_JI_O_K, 11 лет назад, По-русски

Обнаружил не так давно одну интересную проблему с компилятором Microsoft Visual C++ 2010.

Посылка № 4997092 на "acm.timus.ru" от 2 июня 2013 по задаче 1542 получает "Wrong Answer" на первом тесте на компиляторе Visual C++ 2010 и получает Accepted на всех версиях G++.

Я попытался выяснить, в чем проблема. В решении был фрагмент кода:

...
    for (int i=1; i<=k; i++) {
        sch[i] = find_max(a,b);
        update(sch[i], -1);
    }
...

где функции find_max() и update() — для работы с деревом максимумов. С таким фрагментом — "Wrong Answer 1" (на Visual C++ 2010).

Однако! Если добавить никогда не выполняющийся "if" или просто сделать какое-либо действие с sch[i], то получается "Accepted":

...
        for (int i=1; i<=k; i++) {
            sch[i] = find_max(a,b);
            
            if (sch[i] < 0)
               printf("ha-ha-ha"); // if никогда не выполнится (а если бы выполнился,
                                   // то тогда всё равно WA должно быть, а не AC) 
            
            update(sch[i], -1);
        }
...

См. посылку № 4997093 от того же числа.

Как это объяснить? В голову приходит только мысль о том, что оптимизатор Microsoft Visual C++ 2010 просто подсчитал один раз значение функции find_max(a,b) и использовал в дальнейшем его, не вызывая функцию на последующих итерациях цикла, что является неверным, т.к. find_max(a,b) использует дерево tree, изменяющееся в вызовах update(sch[i], -1).

Может быть, есть возможность изменить параметры компиляции, чтобы такого не происходило?

Примечание 1: в ключах компиляции стоит 2-й уровень оптимизации, даже не 3-й. Вроде бы не должно тогда такого происходить.

Примечание 2: на Codeforces такая ошибка тоже проявляется.

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Скорее всего, undefined behavior где-то в коде. Такая конструкция довольно часто используется. Я думаю в случае проблем с оптимизатором уже бы заметили раньше.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Вам прислать код с сэмплами?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Пришлите=)

      → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Проще выложить в открытом доступе. Вряд ли кто-то будет отсылать ваш код, чтобы получить +1 задачу на тимусе.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится -11 Проголосовать: не нравится

        Как проще всего в таком случае выложить код в открытый доступ? Не A+B problem всё-таки.

        Прямо сюда, в обсуждения?

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Ну да. Не настолько это великая задача все-таки, чтобы так скрывать ее. Тем более людям будет проще сразу видеть код, чем выпрашивать его у вас (да и кому это нужно).

          → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Залейте на 10 мин или на час на pastebin.com .

          → Ответить
          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится -10 Проголосовать: не нравится

            Исходный тест:

            5
kare 10
kanojo 20
karetachi 1
korosu 7
sakura 3
3
k
ka
kar

            Правильный ответ:


            kanojo
kare
korosu
karetachi

kanojo
kare
karetachi

kare
karetachi
            → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится -20 Проголосовать: не нравится

        Ок, код программы:

        #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int const maxn = 100100;
int const max_tree = 270000;

int n,m,my_list;
struct node {char name[20]; int num;} s[maxn];
struct elem {int ch,num;} tree[max_tree];
char buf[1000];

int my_strcmp(char const * const a, char const * const b) {
	int i = 0;
	while (a[i] && b[i]) {
		if (a[i] < b[i])
			return -1;
		if (a[i] > b[i])
			return 1;
		i++;
	}
	if (a[i])
		return 1;
	if (b[i])
		return -1;
	return 0;
}

bool operator < (const node &a, const node &b) {
	return my_strcmp(a.name,b.name)<0;
}

int my_less(char const * const a, char const * const b) {
	for (int i=0; a[i] && b[i]; i++)
		if (a[i]<b[i]) return 1;
		else if (a[i]>b[i]) return 0;

	if ((int) strlen(a) < (int) strlen(b)) return 1;
	return 0;
}

int my_more(char const * const a, char const * const b) {
	for (int i=0; a[i] && b[i]; i++)
		if (a[i]>b[i]) return 1;
		else if (a[i]<b[i]) return 0;
	return 0;
}

int my_equal(char const * const a, char const * const b) {
	if ((int) strlen(a) < (int) strlen(b)) return 0;

	for (int i=0; a[i] && b[i]; i++)
		if (a[i]!=b[i]) return 0;
	return 1;
}

void update(int v, int x) {
	v+=my_list;
	tree[v].ch=x; tree[v].num=v-my_list;
	while (v>1) {
		tree[v>>1].ch=max(tree[v].ch,tree[v^1].ch);
		if (tree[v].ch>tree[v^1].ch) tree[v>>1].num=tree[v].num;
		else if (tree[v].ch<tree[v^1].ch) tree[v>>1].num=tree[v^1].num;
		else {
			if (my_strcmp(s[tree[v].num].name,s[tree[v^1].num].name)<0) tree[v>>1].num=tree[v].num;
			else tree[v>>1].num=tree[v^1].num;
		}
		v>>=1;
	}
}

int find_max(int l, int r) {
	int res=-1,num=-1;
	l+=my_list; r+=my_list;
	while (l<=r) {
		if (l%2 == 1) {
			if (tree[l].ch>res) {res=tree[l].ch; num=tree[l].num;}
			else if ((num!=-1) && (tree[l].ch==res) && (my_strcmp(s[tree[l].num].name,s[num].name)<0)) num=tree[l].num;
		}
		if (r%2 == 0) {
			if (tree[r].ch>res) {res=tree[r].ch; num=tree[r].num;}
			else if ((num!=-1) && (tree[r].ch==res) && (my_strcmp(s[tree[r].num].name,s[num].name)<0)) num=tree[r].num;
		}
		l=(l+1)>>1;
		r=(r-1)>>1;
	}
	return num;
}

void do_all(int a, int b, int c) {
	int sch[20];
	
	int k=b-a+1;
	if (10 < k)
		k = 10;

	for (int i=1; i<=k; i++) {
		sch[i] = find_max(a,b);

//if (sch[i] < 0)
//	printf("ha-ha-ha");
		
		update(sch[i], -1);
	}

	for (int i=1; i<=k; i++) {
		printf("%s",s[sch[i]].name);
		if (i<k || (i==k && c<m)) printf("\n");
		update(sch[i],s[sch[i]].num);
	}
	if (c!=m) printf("\n");
}

int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	gets(buf);
	sscanf(buf,"%d",&n);

	for (int i=1; i<=n; i++) {
		gets(buf);
		sscanf(buf,"%s %d",&s[i].name,&s[i].num);
	}

	sort(s+1,s+n+1);
	
	for (my_list=1; my_list<n; my_list*=2);
	my_list--;

	for (int i=1; i<=n; i++)
		update(i,s[i].num);
	
	gets(buf);
	sscanf(buf,"%d",&m);
	
	for (int i=1; i<=m; i++) {
		gets(buf);

		int down=1;
		int up=n;
		int mid, dd1, dd2;

		while (up-1>down) {
			mid=(up+down)/2;
			if (!my_less(s[mid].name,buf)) up=mid;
			else down=mid;
		}
		mid=down;
		
		if (my_equal(s[mid].name,buf)) dd1=mid;
		else {
			mid++;
			if (mid<=n && my_equal(s[mid].name,buf)) dd1=mid;
			else {
				if (i!=m) printf("\n");
				continue;
			}
		}

		down=1; up=n;
		while (up-1>down) {
			mid=(up+down)/2;
			if (!my_more(s[mid].name,buf)) down=mid;
			else up=mid;
		}
		mid=down+1;
		
		if ((mid<=n) && my_equal(s[mid].name,buf)) dd2=mid;
		else dd2=mid-1;
		
		do_all(dd1,dd2,i);
	}
	return 0;
}
        → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Да, вы правы, функция find_max(a,b) почему-то выполняется только 1 раз.

→ Ответить