제출 #677403

#제출 시각아이디문제언어결과실행 시간메모리
677403Cross_Ratio기억 압축 (JOI15_memory)C++14
0 / 100
3685 ms284176 KiB
#include "Memory_lib.h" #include <bits/stdc++.h> using namespace std; int pw[25]; int val(int s, int e, int M) { int val = 0, cnt = 1; for(int i=s;i<e;i++) { val += (M & pw[i])/pw[i] * cnt; cnt *= 2; } return val; } /*string s; char Get(int v) { cout << v << ' '; assert(1<=v&&v<=s.length()); return s[v-1]; }*/ //char Get(int); int Memory(int N, int M) { int i; pw[0] = 1; for(i=1;i<=24;i++) pw[i] = pw[i-1] * 2; int st = val(0, 7, M); int pt = val(7, 14, M); int cnt = val(14, 21, M); int k = val(21, 22, M); //cout << st << ' ' << pt << ' ' << cnt << ' ' << k << '\n'; if(st==pt) { //assert(1<=st+1&&st+1<=N); //assert(cnt==0); if(cnt!=0) return -2; if(st+1>N) return -2; char c = Get(st+1); if(c=='<' || c=='[') { if(st+1>=N) return -2; int v = st + pw[7] * (st+1) + pw[14] * 1 + pw[21] * (c=='<'?1:0); return v; } else { if(st-1<0) return -2; int v = st + pw[7] * (st - 1) + pw[14] * 1 + pw[21] * (c=='>'?1:0); return v; } } if(cnt<=0) return -2; //assert(cnt>=1); if(pt+1>N) return -2; char c = Get(pt+1); //assert(pt+1<=N); if(c=='<'||c=='[') { if(st < pt) { if(pt+1>=N) return -2; int v = st + pw[7] * (pt + 1) + pw[14] * (cnt + 1) + pw[21] * k; return v; } else { // pt < st case if(cnt==1) { int k2 = (c=='<'?1:0); if(k==k2) { if(st+1>=N) return -1; int v = st+1 + pw[7] * (st+1) + pw[14] * 0 + pw[21] * 0; return v; } else return -2; } else { if(pt-1<0) return -2; assert(cnt-1>0); int v = st + pw[7] * (pt - 1) + pw[14] * (cnt - 1) + pw[21] *k; return v; } } } else { // c == '>' || c == ']' if(st<pt) { if(cnt==1) { int k2 = (c=='>'?1:0); if(k==k2) { if(st+1>=N) return -1; int v = st+1 + pw[7] * (st+1) + pw[14] * 0 + pw[21] * 0; return v; } else return -2; } else { if(pt+1>=N) return -2; assert(cnt-1>0); int v = st + pw[7] * (pt+1) + pw[14] * (cnt-1) + pw[21] * k; return v; } } else { // pt < st if(pt-1<0) return -2; int v = st + pw[7] * (pt-1) + pw[14] * (cnt+1) + pw[21] * k; return v; } } } /* signed main() { cin >> s; int cnt = 15000; int M = 0; while(cnt--) { M = Memory(s.length(), M); cout << M << '\n'; if(M==-1) cout << "Right\n"; else if(M==-2) cout << "Wrong\n"; if(M==-1||M==-2) break; } } */ /* #include <stdio.h> #include <stdlib.h> #include <string.h> int Memory(int N, int M); #define MAX_N 100 #define FORMAT_S "%101s" #define LENGTH_S 102 #define LIMIT_M 4194304 // 2^22 #define MAX_NUM_DAYS 15000 static int N, Q; static char S[LENGTH_S]; static void Wrong(int message) { printf("Wrong Answer [%d]\n", message); exit(0); } static int get_called; static int get_I; char Get(int I) { if (get_called) { Wrong(2); } get_called = 1; get_I = I; if (!(1 <= I && I <= N)) { Wrong(3); } return S[I - 1]; } int main(void) { int M; int test_index; int num_days; if (scanf("%d%d", &N, &Q) != 2) { fprintf(stderr, "error: cannot read N, Q\n"); exit(1); } if (!(1 <= N && N <= MAX_N)) { fprintf(stderr, "error: N is out of bounds\n"); exit(1); } if (Q < 0) { fprintf(stderr, "error: Q is out of bounds\n"); exit(1); } for (test_index = 0; test_index < Q; ++test_index) { if (scanf(FORMAT_S, S) != 1) { fprintf(stderr, "error: cannot read S\n"); exit(1); } if (N != (int)strlen(S)) { fprintf(stderr, "error: the length of S is not N\n"); exit(1); } num_days = 0; M = 0; for (; ; ) { get_called = 0; get_I = 0; M = Memory(N, M); if (!((0 <= M && M < LIMIT_M) || M == -1 || M == -2)) { Wrong(1); } if (M == -1 || M == -2) { break; } if (++num_days >= MAX_NUM_DAYS) { Wrong(5); } } printf("%d\n", M); } return 0; } */
#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...