Submission #241769

#	Time	Username	Problem	Language	Result	Execution time	Memory
241769		dsjong	영역 (JOI16_ho_t4)	C++14	15 / 100	73 ms	9976 KiB

2016_ho_t4

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
map<pair<int, int>, bool>mp;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	string s;
	cin>>n>>k>>s;
	assert(k==1 || n<=60);
	int x=0, y=0;
	mp[{0, 0}]=true;
	set<pair<int, int>>v;
	v.insert({0, 0});
	for(int i=0;i<n;i++){
		if(s[i]=='E') x++;
		if(s[i]=='W') x--;
		if(s[i]=='N') y--;
		if(s[i]=='S') y++;
		v.insert({x, y});
	}
	int dy=y, dx=x;
	set<pair<int, int>>v2;
	int cnt=0;
	if(k<=60){
		for(int i=0;i<k;i++){
			for(auto [x, y]:v){
				v2.insert({x+i*dx, y+i*dy});
			}
		}
		for(auto i:v2){
			int x=i.first, y=i.second;
			if(v2.find({x+1, y})!=v2.end() && v2.find({x, y+1})!=v2.end() && v2.find({x+1, y+1})!=v2.end()){
				cnt++;
			}
		}
	}
	else{
		for(int i=0;i<60;i++){
			for(auto [x, y]:v){
				v2.insert({x+i*dx, y+i*dy});
			}
		}
		long long A=0;
		for(auto i:v2){
			int x=i.first, y=i.second;
			if(v2.find({x+1, y})!=v2.end() && v2.find({x, y+1})!=v2.end() && v2.find({x+1, y+1})!=v2.end()){
				A++;
			}
		}
		for(auto [x, y]:v){
			v2.insert({x+60*dx, y+60*dy});
		}
		long long B=0;
		for(auto i:v2){
			int x=i.first, y=i.second;
			if(v2.find({x+1, y})!=v2.end() && v2.find({x, y+1})!=v2.end() && v2.find({x+1, y+1})!=v2.end()){
				B++;
			}
		}
		B-=A;
		cnt=A+B*(k-60);
	}
	cout<<cnt;
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:29:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [x, y]:v){
             ^
2016_ho_t4.cpp:42:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [x, y]:v){
             ^
2016_ho_t4.cpp:53:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for(auto [x, y]:v){
            ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 62