Task: | Tontti |
Sender: | hello_world |
Submission time: | 2015-10-01 22:47:42 +0300 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | TIME LIMIT EXCEEDED | -- | 1 | details |
#2 | ACCEPTED | 0.05 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.04 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | WRONG ANSWER | 0.16 s | 2 | details |
#8 | WRONG ANSWER | 0.39 s | 2 | details |
#9 | WRONG ANSWER | 0.32 s | 2 | details |
#10 | WRONG ANSWER | 0.22 s | 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 3 | details |
#12 | TIME LIMIT EXCEEDED | -- | 3 | details |
#13 | TIME LIMIT EXCEEDED | -- | 3 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3 | details |
#15 | TIME LIMIT EXCEEDED | -- | 3 | details |
Compiler report
input/code.cpp:232:7: warning: "/*" within comment [-Wcomment] }/* ^ input/code.cpp: In function 'int main()': input/code.cpp:57:15: warning: unused variable 'lines' [-Wunused-variable] unsigned int lines = 0; //montako lineä on muistissa ^ input/code.cpp:178:21: warning: unused variable 'const_size' [-Wunused-variable] const unsigned int const_size = min(w, h) - 1; //size on maksimissaa min(leveys - 1, korkeus - 1) = min(leveys, korkeus) - 1 ^ input/code.cpp:179:15: warning: unused variable 'cur_const_size' [-Wunused-variable] unsigned int cur_const_size; ^ input/code.cpp:71:31: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result] fgets(char_line, len, stdin); ^
Code
#include <stdio.h> #include <iostream> #include <string> #include <string.h> #include <stdlib.h> using namespace std; struct Line{ unsigned int *trees_x; //listaa puiden määrän x-suunnassa unsigned int *trees_y; //listaa puiden määrän y-suunnassa unsigned int *r; //matka edelliseen puuhun, joko y-tai x-suunnassa Line *next; Line *last; bool *isTree; }; void printTreesX(Line *ap, unsigned int w); void printTreesY(Line *ap, unsigned int w); void printIsTree(Line *ap, unsigned int w); void printR(Line *ap, unsigned int w); unsigned int count_trees(Line *pointersToLines[], unsigned int y, unsigned int x, unsigned int cur_size); bool isOnTheEdgeOfTheArea(const unsigned int x, const unsigned int y); unsigned int global_w; unsigned int global_h; int main(void){ unsigned int h, w, x; //korkeus, leveys, puiden määrä aluetta kohti cin >> h; //korkes cin >> w; //leveys cin >> x; //puita / alue (voi olla myös nolla, ota se huomioon) if (x < 2) while(1); global_w = w; global_h = h; Line *a = (Line *)malloc(sizeof(Line)); a->next = NULL; a->last = NULL; a->trees_x = (unsigned int *)malloc(sizeof(unsigned int) * w); a->trees_y = (unsigned int *)malloc(sizeof(unsigned int) * w); a->r = (unsigned int *)malloc(sizeof(unsigned int) * w); a->isTree = (bool *)malloc(sizeof(bool) * w); //tämä sisältää pointerit lineihin, jotta ei pidä aina välttämättä toimia ->last:n ja next->n avulla Line *pointersToLines[h]; unsigned int v = w; while(v--) { a->r[v] = 0; //ensimmäisellä rivillä ei ole lähintä matkaa ('oikea yläkulma'), vaan se on aina nolla, sillä lähimmästä matkasta mitataan kuinka paljon pitää kasvattaa kokoa //a->trees_y[v] = 0; //myöskään ensimmäisen rivin yläpuolella ei ole puita } Line *ap = a; unsigned int lines = 0; //montako lineä on muistissa unsigned int len = w + 1; char *char_line = (char*)malloc(sizeof(unsigned int) * len); if (!feof(stdin)) fgetc(stdin); unsigned int i = h; while(i--) { //huomioi, että myös pontersToLines on +:sta -:s suuntaan menevä, kuten lähes kaikki muukin tässä ohjelmassa pointersToLines[i] = ap; //cout << "i:" << i << " " << char_line << endl; fgets(char_line, len, stdin); fgetc(stdin); //katsotaan montako puuta uudella linellä oli, muodostetaan uusi Line unsigned int j = w; unsigned int tree_count = 0; while(j--){ if (char_line[j] == '*') { tree_count++; //lisätään puiden määrää x-suunnassa yhdellä, nopeampi tehdä counterilla kuin samalla tyylillä kuin y:n ap->isTree[j] = true; if (ap->last != NULL) ap->trees_y[j] = (ap->last)->trees_y[j] + 1; //puiden määrä y-suunnassa lisääntyy yhdellä else ap->trees_y[j] = 1; } else { ap->isTree[j] = false; //ei toimi if (ap->last != NULL) { ap->trees_y[j] = (ap->last)->trees_y[j]; //puiden määrä y-suunnassa pysyy samana }else ap->trees_y[j] = 0; } ap->trees_x[j] = tree_count; //rivin alkiosta[ind] rivin loppuun olevien puiden määrä if (j < w - 1){ //j > 0, ei ole ensimmäinen alkio if (ap->last != NULL){ //ei ole ensimmäinen rivi if ((ap->last)->isTree[j]) ap->r[j] = 1; //puu suoraan yläpuolella, joudutaan kasvattamaan kokoa yhdellä jos halutaan saada puu else if (ap->isTree[j + 1]) ap->r[j] = 1; //puu sivulla joudutaan kasvattamaan kokoa yhdellä, jos halutaan saada puu else if ((ap->last)->isTree[j + 1]) ap->r[j] = 1; else { unsigned int m = min((ap->last)->r[j], ap->r[j + 1]); if ((ap->last)->r[j] != 0 || ap->r[j + 1] != 0) ap->r[j] = m + 1; //ei ole aivan puun vieressä, joten etäisyyttä puuhun kasvatetaan yhdellä, kasvatettavaa matkaa lisätään yhdellä else ap->r[j] = m; //jos molemmat y+1 ja x+1 matkat ovat 0, niin myös tämän matka on nolla, muutoin ... +1 } } } else ap->r[j] = 0; } //lasketaan neliöt /*unsigned int v = w; cout << "a->"; while(v--){ cout << ap->trees[v] << " " << endl; }*/ //katsotaan onko lines tarpeeksi suuri, jotta voidaan alkaa muodostamaan neliön muotoisia if (i) { //muodostetaan uusi line, mikäli tarvetta, eli linejen ottamista jatketaan vielä ap->next = (Line *)malloc(sizeof(Line)); (ap->next)->last = ap; ap = ap->next; ap->trees_x = (unsigned int *)malloc(sizeof(unsigned int) * w); ap->trees_y = (unsigned int *)malloc(sizeof(unsigned int) * w); ap->r = (unsigned int *)malloc(sizeof(unsigned int) * w); ap->isTree = (bool *)malloc(sizeof(bool) * w); } //nyt on uusi line jälleen alustettu(ja kenties vanha poistettu) } //nyt on kaikki linet tallessa //cout << endl; printTreesX(ap, w); //cout << endl; printTreesY(ap, w); //cout << endl; printIsTree(ap, w); //cout << endl; printR(ap, w); //cout << endl; printIsTree(pointersToLines[0], w); //määritetään kullekin ruudulle pienin mahdollinen neliön koko, eli että alkaa tulemaan puita /* //saadaan selville kuinka paljon kokoa on minimissään suurennettava, löydetään puita selataan rivi kerrallaan: rivi1: alustetaan nollaksi muut rivit: -jokaisen rivin ensimmäinen alkio on nolla -jokainen alkio on yhden suurempi kuin pienempi kahdesta seuraavasta on -edellisen rivin saman x:n omaava alkio(last, x) -current rivin edellisen y:n omaava alkio(cur, x - 1) */ /* 1.nyt on selvillä jokaisen rivin jokaisen alkion matka(x tai y) lähimpään 'mustaan' alkioon 2.lasketaan kuinka monta puuta on alueella (size = matka) *jos alueella on liian vähän puita: -tarkistetaan kuinka paljon alueen kokoa pitää vielä lisätä *etsitään yläreunaa ja vasenta sivua kiertämällä pienimmän matkan omaava alkio, min(matka, line->matka) */ unsigned int h2, w2; if (x <=1) { //käydään ensimmäinen rivi läpi vain siinä tapauksessa, että omenoiden määrä neliössä on joko 0 tai 1 h2 = h; w2 = w; } else { h2 = h - 1; //muutoin aloitetaan toiselta riviltä, eli a->next w2 = w - 1; } unsigned int cur_size; //mikä on nykyisen line:n nykyisen alkion koko, eli etäisyys x, y puuhun(tai laitaan) unsigned int count_tree; //kuinka monta puuta on tällä hetkellä squaren sisällä unsigned int j = w2; //loopataan 'kaikki' alkiot, mahdollisesti jätetetään ensimmäinen(viimeinen) looppaammatta unsigned int const_count_tree = x; unsigned int count_squares = 0; const unsigned int const_size = min(w, h) - 1; //size on maksimissaa min(leveys - 1, korkeus - 1) = min(leveys, korkeus) - 1 unsigned int cur_const_size; i = h2; while(i--){ //käydään 'jokainen' rivi läpi //pointersToLines[i]->r[j] = aloituskoko, saattaa löytyä ensimmäinen puu, jos tästä ei löydy puita, ei mennä pidemmälle j = w2; while (j--) { //käydään 'jokainen' alkio läpi cur_size = pointersToLines[i]->r[j]; //cout << "line: " << i << " " << j << endl; if (pointersToLines[i]->isTree[j]) count_tree = 1; else count_tree = 0; //käydään jokainen size läpi alkaen cur_size:stä ylöspäin //cur_const_size = min(min(const_size, w - i - 1), h - i - 1); while (true){ count_tree += count_trees(pointersToLines, i, j, cur_size); if (count_tree > const_count_tree){ //puita on liikaa jo tällä size:llä, joten vaihdetaan alkio seuraavaan ja määritetään //sille sitten taas cur_size uudelleen break; //ei tehdä mitään } //cout << i << " " << j << " " << cur_size << " " << count_squares << " " << count_tree << " " << const_count_tree << endl; //jos puita on oikea määrä //cout << i << " " << j << " " << count_tree << " " << cur_size << endl; if (count_tree == const_count_tree) { //puita on juuri oikea määrä //lisätään squarejen määrää yhdellä //kasvatetaan cur_size:ä yhdellä ja katsotaan pysyykö puiden määrä samana //cur_size++; //jos uusia puita ei löydy, eli raja-puiden määrä on nolla, //loopataan niin kauan, kunnes: //joko löytyy uusia puita tai ollaan reunassa, eli global_wall_value = true; count_squares++; //cout << "gotit" << "(" << i << " " << j << ")" << pointersToLines[i]->r[j] << endl; //loopataan niin kauan kuin ollaan alueella ja puiden määrä ei lisäänny /*while (curSize < cur_const_size && !count_trees(pointersToLines, i, j, cur_size) && !isOnTheEdgeOfTheArea(i + cur_size, j + cur_size, h, w)) { count_squares++; cur_size++; }/* //break; //poistutaan, sillä tällä indeksillä, alkiolla ei saada enään squareja millä size:llä */ } //jos puita on liikaa //jos puita on liian vähän //if (count_tree < const_count_tree){ //kasvatetaan kokoa, ja testataan uudelleen //ensin pitää katsoa kuinka paljon kokoa pitää kasvattaa //testaa aluksi, että kasvattaa aina vain yhdellä, jos //nopeus ei riitä, niin ottaa sitten reunoilta pienimmän luvun, //ja kasvattaa sen verran, jos puut ovat harvassa tämä saattaa nopeuttaa ohjelman toimitaa huomattavasti //} cur_size++; //jos päästään loppuun asti, eli puita oli liian vähän, lisätään kokoa } } } //cout << endl; printIsTree(ap, w); //cout << endl << endl << "Trees:" << count_trees(pointersToLines, 0, 0, 3); cout << count_squares; free(char_line); //free(pointersToLines); return 0; } bool isOnTheEdgeOfTheArea(const unsigned int x, const unsigned int y){ return (x == global_w - 1 || y == global_h - 1); } unsigned int count_trees(Line *pointersToLines[], unsigned int y, unsigned int x, unsigned int cur_size){ //jos ollaan niin reunassa, ettei voi olla kuin joko yksi puu tai ei puita ollenkaan if (cur_size == 0) { return 0; // 1 tai 0 } //lasketaan montako puuta löytyy ko.x ja y-koordinaateilla //meillä on tallessa trees_x:ssä ja trees:yssä kuinka paljon 2 const unsigned int const_x = x + cur_size; const unsigned int const_y = y + cur_size; if (const_x >= global_w || const_y >= global_h) { //cout << "const: " << const_x << " " << const_y << endl; return 60000; } unsigned int count_tree_x = pointersToLines[const_y]->trees_x[x] - pointersToLines[const_y]->trees_x[const_x]; //cout << "x: " << count_tree_x << endl; unsigned int count_tree_y = pointersToLines[y]->trees_y[const_x] - pointersToLines[const_y]->trees_y[const_x]; //cout << "y: " << count_tree_y << endl; unsigned int count_tree = count_tree_x + count_tree_y; //cout << "XY: " << count_tree_x << " " << count_tree_y << " " << count_tree << endl; //cout << " x: " << const_x << " p " << pointersToLines[const_y]->trees_x[x] << " " << pointersToLines[const_y]->trees_x[const_x] << " " << x << " " << y << endl; //lasketaan myös kulma-puu mukaan, jos ja vain jos se on olemassa if (pointersToLines[const_y]->isTree[const_x]) count_tree += 1; return count_tree; //palautetaan määrä kutsujalle //tapa 2 //x, x + cur_size //y, y + cur_size //(i, j) /*int i = cur_size + 1; //-> esim. cur_size = 2. i = {2, 1, 0} unsigned int tree_count = 0; const unsigned int const_x = x + cur_size; const unsigned int const_y = y + cur_size; while(i--) { //cur_size:stä nollaan, eli samalle tasolle, missä ollaan //jos löytyy puu, lisätään puiden määrää yhdellä //pidetään aluksi x vakiona:(liikutaan pysty-suunnassa) if (pointersToLines[y]->isTree[const_x]) tree_count++; //pidetään sitten y vakiona:(liikutaan vaaka-suunnassa) if (pointersToLines[const_y]->isTree[x]) tree_count++; } */ //return tree_count; } void printTreesX(Line *ap, unsigned int w){ Line *l = ap; while(l != NULL) { unsigned int w2 = w; cout << "line: "; while (w2--){ cout << l->trees_x[w2] << " "; } cout << endl; l = l->last; cin.get(); } } void printTreesY(Line *ap, unsigned int w){ Line *l = ap; while(l != NULL) { unsigned int w2 = w; cout << "line: "; while (w2--){ cout << l->trees_y[w2] << " "; } cout << endl; l = l->last; cin.get(); } } void printIsTree(Line *ap, unsigned int w){ Line *l = ap; while(l != NULL) { unsigned int w2 = w; cout << "line: "; while (w2--){ cout << l->isTree[w2] << "(" << w2 << ")" << " "; } cout << endl; l = l->last; cin.get(); } } void printR(Line *ap, unsigned int w){ Line *l = ap; while(l != NULL) { unsigned int w2 = w; cout << "line: "; while (w2--){ cout << l->r[w2] << " "; } cout << endl; l = l->last; cin.get(); } } void freeMemory(Line *line){ Line *l; do { l = line; line = line->last; free(l->trees_x); free(l->trees_y); free(l); } while(line->last != NULL); }
Test details
Test 1
Group: 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
10 10 1 ......*... .......*.. *..*....*. *....*.... ... |
correct output |
---|
94 |
user output |
---|
(empty) |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ********** ********** ********** ********** ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 10 **...*...* *..*.**.*. ...**.*..* *...**.*.. ... |
correct output |
---|
4 |
user output |
---|
4 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ****...... *.*.**..** ....*.*..* ...*.***.. ... |
correct output |
---|
16 |
user output |
---|
16 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 2 **.***..*. ...*.*.... .***.*...* ***.***..* ... |
correct output |
---|
30 |
user output |
---|
30 |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 1 ................................. |
correct output |
---|
9552040 |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: WRONG ANSWER
input |
---|
500 500 5 ................................. |
correct output |
---|
1536063 |
user output |
---|
1275268 |
Test 8
Group: 2
Verdict: WRONG ANSWER
input |
---|
500 500 25000 **...*...**..*.*..*.**.*..*.*.... |
correct output |
---|
288 |
user output |
---|
290 |
Test 9
Group: 2
Verdict: WRONG ANSWER
input |
---|
500 500 12500 **.**.*..*...*.**...*.***........ |
correct output |
---|
786 |
user output |
---|
788 |
Test 10
Group: 2
Verdict: WRONG ANSWER
input |
---|
500 500 5000 .*.*.**..*.*.**.**..*..**...*.... |
correct output |
---|
1763 |
user output |
---|
1751 |
Test 11
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 1 ................................. |
correct output |
---|
489611392 |
user output |
---|
(empty) |
Test 12
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 5 ................................. |
correct output |
---|
120725884 |
user output |
---|
(empty) |
Test 13
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
(empty) |
Test 14
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
(empty) |