제출 #239552

#제출 시각아이디문제언어결과실행 시간메모리
239552Ruxandra985Paint By Numbers (IOI16_paint)C++14
90 / 100
976 ms333704 KiB
#include <bits/stdc++.h> #include "paint.h" #define DIMN 200010 using namespace std; int st[200010][110] , dr[200010][110] , sp0[DIMN] , sp1[DIMN]; char v[DIMN]; int white[DIMN] , black[DIMN]; pair <int,int> event[20000010]; string sol; string solve_puzzle(string s, vector<int> c) { int n , k , i , j , ev , cnt , poz; n = s.size(); k = c.size(); for (i = 1 ; i <= n ; i++) v[i] = s[i - 1]; for (i = 1 ; i <= n ; i++){ sp0[i] = sp0[i - 1]; sp1[i] = sp1[i - 1]; if (s[i - 1] == '_') sp0[i]++; else if (s[i - 1] == 'X') sp1[i]++; } /// MAI SUNT NISTE CONDITII PT ALEA PRESTABILITE !!!!!!!!! st[0][0] = 1; /// st[i][j] = pot sa pun primele j seturi pe poz 1 .. i?? for (i = 1 ; i <= n ; i++){ if (sp1[i] == 0) st[i][0] = 1; for (j = 1 ; j <= k ; j++){ if (v[i] != 'X') st[i][j] = st[i - 1][j]; /// altfel, inchei setul i pe pozitia j, DACA POT if (i - c[j - 1] - 1 == -1 && sp0[i] == 0 && v[i + 1] != 'X' && j == 1){ st[i][j] = 1; } if (i - c[j - 1] - 1 >= 0 && v[i - c[j - 1]] != 'X' && sp0[i] - sp0[i - c[j - 1]] == 0 && v[i + 1] != 'X') st[i][j] = (st[i][j] | st[i - c[j - 1] - 1][j - 1]); } } dr[n + 1][k + 1] = 1; dr[n + 2][k + 1] = 1; /// dr[i][j] = pot sa pun seturile j ... k pe poz i ... n ? for (i = n ; i ; i--){ if (sp1[n] - sp1[i - 1] == 0) dr[i][k + 1] = 1; for (j = k ; j ; j--){ if (v[i] != 'X') dr[i][j] = dr[i + 1][j]; /// altfel, incep setul j pe pozitia i, daca pot if (i + c[j - 1] <= n+1 && v[i + c[j - 1]] != 'X' && sp0[i + c[j - 1] - 1] - sp0[i - 1] == 0 && v[i - 1] != 'X') dr[i][j] = (dr[i][j] | dr[i + c[j - 1] + 1][j + 1]); } } ev = 0; for (i = 1 ; i <= n ; i++){ for (j = 1 ; j <= k ; j++){ /// poate sa se termine pe pozitia i setul j? if (i - c[j - 1] - 1 >= 0 && v[i - c[j - 1]] != 'X' && sp0[i] - sp0[i - c[j - 1]] == 0 && v[i + 1] != 'X' && st[i - c[j - 1] - 1][j - 1] && dr[i + 2][j + 1]){ event[++ev] = make_pair(i - c[j - 1] + 1 , 1); event[++ev] = make_pair (i + 1 , -1); } else if (i - c[j - 1] == 0 && j == 1 && sp0[i] == 0 && v[i + 1] != 'X' && dr[i + 2][j + 1]){ event[++ev] = make_pair(1 , 1); event[++ev] = make_pair(i + 1 , -1); } if ((st[i - 1][j] && dr[i + 1][j + 1]) || (st[i - 1][j - 1] && dr[i + 1][j])) white[i] = 1; //if (i == 7 && white[i] == 1) // printf ("a"); } } sort (event + 1 , event + ev + 1); cnt = 0; poz = 1; for (i = 1 ; i <= n ; i++){ while (poz <= ev && event[poz].first == i){ cnt += event[poz].second; poz++; } if (cnt) black[i] = 1; } for (i = 1 ; i <= n ; i++){ if (v[i] != '.') sol.push_back(v[i]); else { if (black[i] && white[i]) sol.push_back('?'); else if (black[i]) sol.push_back('X'); else if (white[i]) sol.push_back('_'); } } return sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...