제출 #975797

#제출 시각아이디문제언어결과실행 시간메모리
975797ALeonidou죄수들의 도전 (IOI22_prison)C++17
0 / 100
1 ms772 KiB
#include "prison.h" #include <bits/stdc++.h> using namespace std; #define ll int #define sz(x) (ll)x.size() #define F first #define S second #define endl "\n" #define pb push_back typedef vector <ll> vi; typedef pair <ll,ll> ii; typedef vector <ii> vii; #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for(ll i =0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } void printVct2D(vector <vi> v){ for (ll i =0; i<sz(v); i++){ cout<<i<<": "; for(ll j =0;j<sz(v[i]); j++){ cout<<v[i][j]<<" "; } cout<<endl; } } ll getAns(ll bag_that_is_less){ if (bag_that_is_less == 0) return -1; return -2; } vector<vi> devise_strategy(int n) { //STEP 1: pre-calculate the 3-base representation of all numbers from 0 to 5000 ll p3[8]; p3[0] = 1; for (ll i =1; i<=7; i++){ p3[i] = p3[i-1] * 3; } vector < vi > b3(5001, vi(8,0)); for (ll i =1; i<=5000; i++){ ll num = i; for (ll pos = 7; pos >= 0; pos--){ b3[i][pos] = num / p3[pos]; num -= b3[i][pos] * p3[pos]; } } cout<<"1: "; printVct(b3[1]); cout<<"3: "; printVct(b3[3]); cout<<"4: "; printVct(b3[4]); vector <vi> s(23, vi(n+1)); //STEP 2: Construct first row ll firstRow = 1; s[0][0] = 0; s[0][1] = -1; s[0][n] = -2; for (ll i =1; i<=n; i++){ ll d = b3[i][7]; // dbg2(i,d); if (d == 0) s[0][i] = firstRow; else if (d == 1) s[0][i] = firstRow+1; else if (d == 2) s[0][i] = firstRow+2; } // printVct2D(s); //STEP 3: Construct first 7 full row ll curBag = 1; //0=A, 1=B for (ll curDigit = 7; curDigit>0; curDigit--){ firstRow += 3; for (ll row = 0; row<3; row++){ //loop throug all rows current digit ll rowIdx = (7-curDigit) * 3 + row + 1; s[rowIdx][0] = curBag; for (ll i = 1; i<=n; i++){ ll d = b3[i][curDigit]; if (d < row) s[rowIdx][i] = getAns(curBag); else if (d > row) s[rowIdx][i] = getAns(!curBag); else{ ll d2 = b3[i][curDigit-1]; if (curDigit != 1){ if (d2 == 0) s[rowIdx][i] = firstRow; else if (d2 == 1) s[rowIdx][i] = firstRow+1; else if (d2 == 2) s[rowIdx][i] = firstRow+2; } else{ //second last row if (d2 == 0) s[rowIdx][i] = getAns(curBag); else if (d2 == 1) s[rowIdx][i] = firstRow; else if (d2 == 2) s[rowIdx][i] = getAns(!curBag); } } } } curBag = !curBag; } //STEP 4: Construct last row const int lastRow = 22; curBag = 0; s[lastRow][0] = curBag; for (ll i =1; i<=n; i++){ ll d = b3[i][0]; if (d == 0) s[lastRow][i] = getAns(curBag); else if (d == 2) s[lastRow][i] = getAns(!curBag); //d = 1 is not possible } // printVct2D(s); return s; } /* 5 3 4 -1 2 1 2 -1 5000 3 4 2 5 4 1 245 234 12 2304 4019 4000 -1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...