oj.uz

Submission #723611

# Submission time Handle Problem Language Result Execution time Memory
723611 2023-04-14T06:17:50 Z Darren0724 Legendary Dango Maker (JOI20_dango2) Text
85 / 100
 0 ms 0 KB 
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx","avx2")
#include<bits/stdc++.h>
using namespace std;

int main(){
    int goal=46500;
    freopen("dango2/input_06.txt","r",stdin);
    ofstream fout;
    fout.open("dango2/ouput_06.txt");
    int n,m;cin>>n>>m;
    vector<string> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int> dx={-1,-1,-1,0,0,1,1,1},dy={-1,0,1,-1,1,-1,0,1};
    vector<vector<int>> dango;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(v[i][j]!='W'){
                continue;
            }
            for(int k=0;k<8;k++){
                int i1=i+dx[k],j1=j+dy[k];
                int i2=i+dx[7-k],j2=j+dy[7-k];
                if(i1<0||i1>=n||j1<0||j1>=m||i2<0||i2>=n||j2<0||j2>=m){
                    continue;
                }
                if(v[i1][j1]!='P'||v[i2][j2]!='G'){
                    continue;
                }
                //cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<' '<<i2<<' '<<j2<<' '<<endl;
                vector<int> tmp={i1,j1,i,j,i2,j2,k,0};
                dango.push_back(tmp);
            }
        }
    }
    int rec[501][501];
    for(int i=0;i<=500;i++){
        for(int j=0;j<=500;j++){
            rec[i][j]=-1;
        }
    }
    int ans=0;
    int sz=dango.size();
    //cout<<sz<<endl;
    cout<<fixed<<setprecision(10);
    for(int __=0;__<777771449;__++){
        long double d=0.0001;
        mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
        for(long long _=0;_<7777771449;_++){
            if(_%5000000==0){
                cout<<__<<' '<<_<<' '<<ans<<' '<<d<<endl;
            }
            //cout<<ans<<endl;
            int id;
            id=uniform_int_distribution<int>(0,sz-1)(rnd);
            if(dango[id][7]){
                continue;
            }
            int cnt=0;
            if(rec[dango[id][0]][dango[id][1]]!=-1){
                cnt++;
            }
            if(rec[dango[id][2]][dango[id][3]]!=-1){
                cnt++;
            }
            if(rec[dango[id][4]][dango[id][5]]!=-1){
                cnt++;
            }
            bool flag=0;
            if(cnt>=3){
                int p=uniform_int_distribution<int>(1,1000000000)(rnd);
                if(p<=d*100000000){
                    d*=0.99999;
                    flag=1;
                    ans-=cnt;
                }
                //flag=0;
            }
            else if(cnt==2){
                int p=uniform_int_distribution<int>(1,1000000000)(rnd);
                if(p<=d*1000000000){
                    d*=0.99999;
                    flag=1;
                    ans-=cnt;
                }
                //flag=0;
            }
            else if(cnt==1){
                //int p=uniform_int_distribution<int>(1,1000000000)(rnd);
                flag=1;
                ans--;
            }
            else{
                flag=1;
            }
            if(!flag){
                continue;
            }
            ans++;
            if(rec[dango[id][0]][dango[id][1]]!=-1){
                int id1=rec[dango[id][0]][dango[id][1]];
                dango[id1][7]=0;
                rec[dango[id1][0]][dango[id1][1]]=-1;
                rec[dango[id1][2]][dango[id1][3]]=-1;
                rec[dango[id1][4]][dango[id1][5]]=-1;
            }
            if(rec[dango[id][2]][dango[id][3]]!=-1){
                int id1=rec[dango[id][2]][dango[id][3]];
                dango[id1][7]=0;
                rec[dango[id1][0]][dango[id1][1]]=-1;
                rec[dango[id1][2]][dango[id1][3]]=-1;
                rec[dango[id1][4]][dango[id1][5]]=-1;
            }
            if(rec[dango[id][4]][dango[id][5]]!=-1){
                int id1=rec[dango[id][4]][dango[id][5]];
                dango[id1][7]=0;
                rec[dango[id1][0]][dango[id1][1]]=-1;
                rec[dango[id1][2]][dango[id1][3]]=-1;
                rec[dango[id1][4]][dango[id1][5]]=-1;
            }
            for(int j=0;j<3;j++){
                rec[dango[id][j*2]][dango[id][j*2+1]]=id;
            }
            dango[id][7]=1;
            if(ans>=goal){
                cout<<ans<<endl;
                char c[8]={'\\','|','/','-','-','/','|','\\'};
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        if(rec[i][j]==-1){
                            fout<<v[i][j];
                        }
                        else{
                            int id=rec[i][j];
                            if(dango[id][2]==i&&dango[id][3]==j){
                                fout<<c[dango[id][6]];
                            }
                            else{
                                fout<<v[i][j];
                            }
                        }
                    }
                    fout<<endl;
                }
                fout.close();
                exit(0);
            }
        }
    }
    cout<<ans<<endl;
    char c[8]={'\\','|','/','-','-','/','|','\\'};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(rec[i][j]==-1){
                fout<<v[i][j];
            }
            else{
                int id=rec[i][j];
                if(dango[id][2]==i&&dango[id][3]==j){
                    fout<<c[dango[id][6]];
                }
                else{
                    fout<<v[i][j];
                }
            }
        }
        fout<<endl;
    }


    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 0 KB Token parameter [name=S_1] equals to "#pragma", doesn't correspond to pattern "[PWG\|\-\\/]{500}"
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 0 KB Output is correct. N = 41980

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 0 KB Output is correct. N = 51390

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 0 KB Output is correct. N = 19120

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 0 KB Output is correct. N = 48620

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 0 KB Output is correct. N = 46500